110: 平衡二叉树

给定一个二叉树，判断它是否是高度平衡的二叉树。 本题中，一棵高度平衡二叉树定义为： 一个二叉树每个节点的左右两个子树的高度差的绝对值不超过1。

示例：
给定二叉树 [3,9,20,null,null,15,7]

    3
   / \
  9  20
    /  \
   15   7

返回 true 。

给定二叉树 [1,2,2,3,3,null,null,4,4]

       1
      / \
     2   2
    / \
   3   3
  / \
 4   4

返回false。

思路：

平衡二叉树的话，要判定每一个非叶子结点的左右子树的高度差的绝对值是否控制在1以内。注意要对每个叶子结点都要做判定。所以我们要做的是在获取树高的基础上进行一下比较一下高度差是否大于1.

实现方式1：
递归 - 缺点是会使用大量的内存空间。

实现方式2：
用一个栈来保存结点，从底部开始向上部计算。不符合条件直接return False。
缺点是会进行大量的重复运算。(当然啦，可以优化，吃完饭搞一搞，用动态规划的思想可以搞定,即利用部分计算的结果来往上推测。懒得写了…) 改进后的思路就是用二叉树的顺序存储法，对结点增设left_tree_height和right_tree_height。叶子结点的left_tree_height和right_tree_height的值为0.然后我们就可以方便的往上推了。

实现方式1的代码：

class Solution:
    def isBalanced(self, root) -> bool:
        def balance(node):
            if node is None:
                return True,0
            ltf,ltn = balance(node.left)
            if not ltf:
                return ltf,0
            rtf,rtn = balance(node.right)
            if not rtf:
                return rtf,0
            return ltf and rtf and abs(ltn-rtn) <= 1, (1 + ltn) if ltn > rtn else (1 + rtn)
        return balance(root)[0]

实现方式2的代码：

class Solution:
    # def isBalanced(self, root) -> bool:
    #     def balance(node):
    #         if node is None:
    #             return True,0
    #         ltf,ltn = balance(node.left)
    #         if not ltf:
    #             return ltf,0
    #         rtf,rtn = balance(node.right)
    #         if not rtf:
    #             return rtf,0
    #         return ltf and rtf and abs(ltn-rtn) <= 1, (1 + ltn) if ltn > rtn else (1 + rtn)
    #     return balance(root)[0]
    def isBalanced(self, root) -> bool:
        def get_depth(node):
            if node is None:
                return 0
            left_height = get_depth(node.left)
            right_height = get_depth(node.right)
            return 1 + left_height if left_height > right_height else 1 + right_height
        stack_node = []
        queue_node = [root]
        if root is None:
            return True
        while len(queue_node): # 层序入栈
            front = queue_node.pop(0)
            if front.left:
                queue_node.append(front.left)
            if front.right:
                queue_node.append(front.right)
            stack_node.append(front)
        while len(stack_node):
            cur_node = stack_node.pop(-1)
            if abs(get_depth(cur_node.left) - get_depth(cur_node.right)) > 1:
                return False
        return True