面试题55 - II. 平衡二叉树

平衡二叉树

题目描述

输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。

---

示例：

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

返回 true 。

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

返回 false 。

---

提示：
1 <= 树的结点个数 <= 10000

转载来源：力扣（LeetCode）

---

题目分析

这题明显需要对比一个节点的左子树的深度和右子树的深度，而获取树的深度用递归很简单就能实现，在获取树的深度之后，如果当前节点的左右子树深度相差不大与1，那么对于当前节点来说是平衡的，但是对于它的左子树和右子树是不是都平衡，这是不知道的，所以还要继续求，这可以用下面的流程来表示：

1. 获取当前节点的左子树深度和右子树深度
2. 比较左右子树深度
     - 如果深度差大于1，不平衡，返回false
     - 如果深度差小于等于1，平衡，分别以当前节点的左右孩子为root 执行步骤1，返回两个结果的与；

 public boolean isBalanced(TreeNode root) {
        if(root == null)
            return true;
        int ld = getDeep(root.left);
        int rd = getDeep(root.right);
        if(Math.abs(ld - rd) > 1)
            return false;
        return isBalanced(root.left) && isBalanced(root.right);
    }

    public int getDeep(TreeNode root){
        if(root == null)
            return 0;
        int leftDeep = getDeep(root.left);
        int rightDeep = getDeep(root.right);
        return (leftDeep > rightDeep) ? 1+leftDeep : 1+rightDeep;
    }

我们很容易就发现，父节点的getDeep的时候，会往下探索深度，而子节点getDeep的时候，也会往下探索深度，这就造成了很多重复计算，我觉得这会使得程序变得慢很多，时间复杂度是O(N*logN），但是在LeetCode上还是击败了100%的用户，耗时1ms，然后我就改一下，换成从下往上的思路，看到这些重复的计算，看看效果怎么样；

由下往上的思路大概如下所示：

1. 从获取根节点的左子树深度和右子树深度
2. 节点获取深度的时候也需要获取左右节点深度，如果当前节点不平衡，设置标志位false，直接返回0，他的父节点收到这个标志位的信号的时候，也不在意左右子树深度了，因为某个子树已经不平衡了，直接返回0就好

boolean balance = true;
    public boolean isBalanced2(TreeNode root){
        if(root == null)
            return true;
        int ld = getDeep(root.left);
        if(!balance)
            return false;
        int rd = getDeep(root.right);
        if(Math.abs(ld - rd) > 1)
            return false;
        return balance;
    }

    public int getDeep2(TreeNode root){
        if(root == null || !balance)
            return 0;
        int leftDeep = getDeep(root.left);
        if(!balance)
            return 0;
        int rightDeep = getDeep(root.right);
        if(!balance || Math.abs(leftDeep - rightDeep) > 1) {
            balance = false;
            return 0;
        }
        return (leftDeep > rightDeep) ? 1+leftDeep : 1+rightDeep;
    }

代码文件

---