【Leetcode】110. Balanced Binary Tree 解题报告

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

方法1 递归

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

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

    def getHeight(self, root):
        if root == None:
            return 0
        else:
            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) != -1

    def  getHeight(self,root):
        if root == None:
            return 0
        l = self.getHeight(root.left)
        if l == -1:
            return -1
        r = self.getHeight(root.right)
        if r == -1:
            return -1
        if abs(l - r) > 1:
            return -1
        else:
            return max(l, r)+1

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

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

class Solution3:
    def isBalanced(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        if root == None:
            return True
        stack = []
        prev = None
        pNode = root
        while(len(stack) or pNode):
            if pNode != None:
                stack.append(pNode)
                pNode = pNode.left
            else:
                pNode = stack[-1]
                if pNode.right == prev or pNode.right == None:
                    stack.pop()
                    prev = pNode
                    if pNode.left == None or pNode.right == None:
                        if pNode.left == None and pNode.right == None:
                            pNode.val = 1
                        else:
                            node = pNode.left if pNode.left != None else pNode.right
                            if node.val >=2:
                                return False
                            pNode.val = node.val +1
                    else:
                        l = pNode.left.val
                        r = pNode.right.val
                        if abs(l -r) >1 :
                            return False
                        else:
                            pNode.val  = max(pNode.left.val, pNode.right.val) +1
                    pNode = None
                else:
                    pNode = pNode.right
        return 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.left
            else:
                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 False
                    else:
                        dictionary[pNode] = max(l, r) +1
                    prev =  pNode
                    pNode = None
                else:
                    pNode = pNode.right
        return True