怎么做点击图片跳转网站/百度排行榜明星

判断一个树是不是平衡二叉树

方法1 递归

对于某个节点。求其左右子树的高度差，如果满足，再递归的判断左右子树。这是一种自顶而下的方法

class Solution1:def isBalanced(self, root):""":type root: TreeNode:rtype: bool"""if root == None:return Trueelse:if abs(self.getHeight(root.left) -  self.getHeight(root.right)) <=1:return  self.isBalanced(root.left) and self.isBalanced(root.right)else:return Falsedef getHeight(self, root):if root == None:return 0else:return max(self.getHeight(root.left), self.getHeight(root.right))+1

方法2 改进版递归

上面的方法重复计算了很多节点的深度，我们可以自底向上，如果不满足就返回-1，判断根节点的返回值即可。

class Solution2:def isBalanced(self, root):""":type root: TreeNode:rtype: bool"""return self.getHeight(root) != -1def  getHeight(self,root):if root == None:return 0l = self.getHeight(root.left)if l == -1:return -1r = self.getHeight(root.right)if r == -1:return -1if abs(l - r) > 1:return -1else:return max(l, r)+1

方法三 非递归 需要修改节点的val

非递归法主要通过栈来完成，是一个自底向上的过程，最难的过程就是子节点的深度确定后如何确定父节点的深度
一个方法是修改节点的值为该节点自底向上的深度，即方法三
另一个方法就是讲节点的深度保存到一个map里，即方法四

class Solution3:def isBalanced(self, root):""":type root: TreeNode:rtype: bool"""if root == None:return Truestack = []prev = NonepNode = rootwhile(len(stack) or pNode):if pNode != None:stack.append(pNode)pNode = pNode.leftelse:pNode = stack[-1]if pNode.right == prev or pNode.right == None:stack.pop()prev = pNodeif pNode.left == None or pNode.right == None:if pNode.left == None and pNode.right == None:pNode.val = 1else:node = pNode.left if pNode.left != None else pNode.rightif node.val >=2:return FalsepNode.val = node.val +1else:l = pNode.left.valr = pNode.right.valif abs(l -r) >1 :return Falseelse:pNode.val  = max(pNode.left.val, pNode.right.val) +1pNode = Noneelse:pNode = pNode.rightreturn True

方法四 非递归 map作为辅助空间

class Solution4:def isBalanced(self, root):""":type root: TreeNode:rtype: bool"""pNode, prev, dictionary, stack = root, None, {}, []while(len(stack) or pNode):if pNode:stack.append(pNode)pNode = pNode.leftelse:pNode = stack[-1]if pNode.right == None or pNode.right == prev:stack.pop()l = dictionary.get(pNode.left, 0)r = dictionary.get(pNode.right, 0)if abs(l - r) > 1:return Falseelse:dictionary[pNode] = max(l, r) +1prev =  pNodepNode = Noneelse:pNode = pNode.rightreturn True