0%

leetcode每日一题-平衡二叉树

Posted on In ,

平衡二叉树

image1

方法一：自顶向下递归

定义函数height，用于计算二叉树的高度：

  1. 如果p是空节点，那么height(p) = 0。
  2. 如果p非空，那么height(p)=max(height(p.left),height(p.right))+1。

有了计算节点高度的函数，即可判断二叉树是否平衡。具体做法类似于二叉树的前序遍历，即对于当前遍历到的节点，首先计算左右子树的高度，如果左右子树的高度差是否不超过 11，再分别递归地遍历左右子节点，并判断左子树和右子树是否平衡。这是一个自顶向下的递归的过程。

1
/**
2
 * Definition for a binary tree node.
3
 * public class TreeNode {
4
 *     int val;
5
 *     TreeNode left;
6
 *     TreeNode right;
7
 *     TreeNode(int x) { val = x; }
8
 * }
9
 */
10
class Solution {
11
    public boolean isBalanced(TreeNode root) {
12
        if(root == null){
13
            return true;
14
        }
15
        boolean res = Math.abs(height(root.left)-height(root.right))<=1 ? true : false;
16
        return isBalanced(root.left) && isBalanced(root.right) && res;
17
    }
18
19
    public int height(TreeNode root){
20
        if(root == null){
21
            return 0;
22
        }
23
        if(root.left==null && root.right==null){
24
            return 1;
25
        }
26
        int h = Math.max(height(root.left),height(root.right))+1;
27
        return h;
28
    }
29
}

复杂度分析：

  • 时间复杂度：$O(n^2)$，最坏情况下二叉树是链式结构，高度为$O(n)$。
  • 空间复杂度：$O(n)$。

方法二：自底向上的递归

方法一由于是自顶向下递归，因此对于同一个节点，函数 height 会被重复调用，导致时间复杂度较高。如果使用自底向上的做法，则对于每个节点，函数 height 只会被调用一次。

自底向上递归的做法类似于后序遍历，对于当前遍历到的节点，先递归地判断其左右子树是否平衡，再判断以当前节点为根的子树是否平衡。如果一棵子树是平衡的，则返回其高度（高度一定是非负整数），否则返回 -1−1。如果存在一棵子树不平衡，则整个二叉树一定不平衡。

1
/**
2
 * Definition for a binary tree node.
3
 * public class TreeNode {
4
 *     int val;
5
 *     TreeNode left;
6
 *     TreeNode right;
7
 *     TreeNode(int x) { val = x; }
8
 * }
9
 */
10
class Solution {
11
    public boolean isBalanced(TreeNode root) {
12
        if(root == null){
13
            return true;
14
        }
15
        return height(root)>=0;
16
    }
17
18
    public int height(TreeNode root){
19
        if(root == null){
20
            return 0;
21
        }
22
        int leftHeight = height(root.left);
23
        int rightHeight = height(root.right);
24
        if(leftHeight==-1 || rightHeight==-1 || Math.abs(leftHeight-rightHeight)>1){
25
            return -1;
26
        }
27
        return Math.max(leftHeight, rightHeight)+1;
28
    }
29
}

复杂度分析：

  • 时间复杂度：$O(n)$。
  • 空间复杂度：$O(n)$。