110. Balanced Binary Tree

思路：构造一个height函数，计算每个节点的高度，然后递归比较左右子树的高度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def isBalanced(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        # 6 star, 多加练习
        # 
        if not root:
            return True
        if abs(self.height(root.left)-self.height(root.right)) <= 1:
            return self.isBalanced(root.left) and self.isBalanced(root.right)
        return False

    def height(self, node):
        if not node:
            return 0
        return max(self.height(node.left), self.height(node.right)) + 1

Go:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
func isBalanced(root *TreeNode) bool {
	var leftHeight, rightHeight int
	if root == nil || (root.Left == nil && root.Right == nil) {
		return true
	}
	if root.Left != nil {
		leftHeight = getHeight(root.Left) + 1
	}
	if root.Right != nil {
		rightHeight = getHeight(root.Right) + 1
	}

	if math.Abs(float64(leftHeight)-float64(rightHeight)) > 1.0 {
		return false
	}
	return isBalanced(root.Left) && isBalanced(root.Right)

}
func getHeight(node *TreeNode) int {
	var leftHeight, rightHeight int
	if node.Left == nil && node.Right == nil{
		return 0
	}
	if node.Left != nil {
		leftHeight = getHeight(node.Left) + 1
	}
	if node.Right != nil {
		rightHeight = getHeight(node.Right) + 1
	}
	if leftHeight > rightHeight {
		return leftHeight
	} else {
		return rightHeight
	}
}