Given a binary tree, determine if it is height-balanced.
For this problem, a height-balanced binary tree is defined as:
a binary tree in which the left and right subtrees of every node differ in height by no more than 1.
Example 1:
Given the following tree [3,9,20,null,null,15,7]
:
3 / \ 9 20 / \ 15 7
Return true.
Example 2:
Given the following tree [1,2,2,3,3,null,null,4,4]
:
1 / \ 2 2 / \ 3 3 / \ 4 4
这个题很明显是用DFS做,问题在于深度信息怎么传递,本来我想着在TreeNode中加一个变量信息
但这样明显有违题意,所以代码中采用了新的函数return直接返回深度或者-1,返回-1并不代表深度,只是
表示程序结束了。此外还是设置了一个类内全局变量来表示,这个题的延伸或者说目前的简单之处就在于
他只问你是否平衡而不需要问具体深度,所以只要用一个变量表示平衡,然后判断当数值不平衡时,改变变量即可
class TreeNode(object): def __init__(self,x): self.val=x self.left=None self.right=None class Solution(object): def isBalanced(object,root): self.balanced=True def height(root): if not root or not self.balanced: return -1 l=height(root.left) r=height(root.right) if abs(l-r)>1: self.balanced=False return -1 return max(l,r)+1 height(root) return self.balanced