平衡二叉树.md

平衡二叉树

知识点：

题目描述

输入一棵二叉树，判断该二叉树是否是平衡二叉树。

解题思路

遍历每个结点，借助一个获取树深度的递归函数，根据该结点的左右子树高度差判断是否平衡，然后递归地对左右子树进行判断,但是如果直接用传统的求二叉树深度的方法有很明显的问题，在判断上层结点的时候，会多次重复遍历下层结点，增加了不必要的开销。如果改为从下往上遍历，如果子树是平衡二叉树，则返回子树的高度；如果发现子树不是平衡二叉树，则直接停止遍历，这样至多只对每个结点访问一次。

代码

    def TreeDepth(self, pRoot):
        # write code here
        if pRoot is None:
            return 0

        deepth1 = self.TreeDepth(pRoot.left)
        if deepth1==-1:
            return -1
        deepth2 = self.TreeDepth(pRoot.right)
        if deepth2==-1:
            return -1
        if abs(deepth1 - deepth2) > 1:
            return -1
        return max(1 + deepth1, 1 + deepth2)

    def IsBalanced_Solution(self, pRoot):
        # write code here
        if pRoot is None:
            return True
        deepth1 = self.TreeDepth(pRoot)

        if deepth1 == -1:
            return False
        return True

这里