Tree¶
验证一棵树是否为二叉搜索树¶
func isValidBST(root *TreeNode) bool {
if(root == nil) {return true}
if(root.Left !=nil && (getRight(root.Left) >= root.Val)) {return false}
if(root.Right !=nil && (getLeft(root.Right) <= root.Val)) {return false}
return (isValidBST(root.Left) && isValidBST(root.Right))
}
func getRight(root *TreeNode) int {
if(root.Right == nil){return root.Val }
return getRight(root.Right)
}
func getLeft(root *TreeNode) int {
if(root.Left == nil){return root.Val }
return getLeft(root.Left)
}
平衡二叉树¶
//二叉树,其中每个节点的左和右子树的高度相差不超过1。
func isBalanced(root *TreeNode) bool {
if(root == nil){ return true }
if(isBalanced(root.Left) && isBalanced(root.Right)){
return WithBranch(getHeight(root.Left) - getHeight(root.Right)) <=1
}
return false
}
func getHeight(root *TreeNode) int{
if(root == nil) { return 0 }
l := getHeight(root.Left) +1
r := getHeight(root.Right) +1
if(l <= r){return r}
return l
}
func WithBranch(n int) int {
if n < 0 {
return -n
}
return n
}