110. 平衡二叉树

柔情只为你懂 2023-10-15 21:29 11阅读 0赞

### 110. 平衡二叉树 ###

*  1. 题目描述
 *  2. 补充内容
 *  3. 本题思路
 *   *  3.1 递归
     *   *  3.1.1 明确递归函数的参数和返回值
         *  3.1.2 明确终止条件
         *  3.1.3 明确单层递归的逻辑
     *  3.2 迭代
 *  4. 总结
 *  5. 具体代码实现
 *   *  5.1 递归法
     *  5.2 迭代法
     *  5.3 优化迭代法

# 1. 题目描述 #

[力扣入口-110. 平衡二叉树][-110.]

给定一个二叉树，判断它是否是高度平衡的二叉树。

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

示例 1:

给定二叉树 \[3,9,20,null,null,15,7\]  
给定一个二叉树，判断它是否是高度平衡的二叉树。

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

示例 1:

给定二叉树 \[3,9,20,null,null,15,7\]  
![在这里插入图片描述][9d3310f3b63a4139b3cead2801c8c259.png]  
返回 true 。

示例 2:

给定二叉树 \[1,2,2,3,3,null,null,4,4\]  
![在这里插入图片描述][fe0240273b8646da89be1872c40a27ea.png]  
返回false。

# 2. 补充内容 #

本题似乎和 [104.二叉树的最大深度][104.] 很像，但是有很大的区别。

这里强调一波概念：

*  二叉树节点的深度：指从根节点到该节点的最长简单路径边的条数。
 *  二叉树节点的高度：指从该节点到叶子节点的最长简单路径边的条数。

但leetcode中强调的深度和高度很明显是按照节点来计算的，如图：  
![在这里插入图片描述][2411bf4bcb4944b89184fd4c99dd7286.png]  
关于根节点的深度究竟是1 还是 0，不同的地方有不一样的标准，leetcode的题目中都是以节点为一度，即根节点深度是1。但维基百科上定义用边为一度，即根节点的深度是0，我们暂时以leetcode为准（毕竟要在这上面刷题）。

因为求深度可以从上到下去查 所以需要前序遍历（中左右），而高度只能从下到上去查，所以只能后序遍历（左右中）

有的同学一定疑惑，为什么 [104.二叉树的最大深度][104.] 中求的是二叉树的最大深度，也用的是后序遍历。

那是因为代码的逻辑其实是求的根节点的高度，而根节点的高度就是这棵树的最大深度，所以才可以使用后序遍历。

# 3. 本题思路 #

## 3.1 递归 ##

此时大家应该明白了既然要求比较高度，必然是要后序遍历。

### 3.1.1 明确递归函数的参数和返回值 ###

参数：当前传入节点。  
返回值：以当前节点为根节点的树的高度。

那么如何标记左右子树是否差值大于1呢？  
如果当前传入节点为根节点的二叉树已经不是二叉平衡树了，还返回高度的话就没有意义了。  
所以如果已经不是二叉平衡树了，可以返回-1 来标记已经不符合平衡树的规则了。

代码如下：

// -1 表示已经不是平衡二叉树了，否则返回值是以该节点为根节点树的高度
    int getHeight(TreeNode* node)

### 3.1.2 明确终止条件 ###

递归的过程中依然是遇到空节点了为终止，返回0，表示当前节点为根节点的树高度为0。  
代码如下：

if (node == NULL) {
        
        return 0;
    }

### 3.1.3 明确单层递归的逻辑 ###

如何判断以当前传入节点为根节点的二叉树是否是平衡二叉树呢？当然是其左子树高度和其右子树高度的差值。

分别求出其左右子树的高度，然后如果差值小于等于1，则返回当前二叉树的高度，否则返回-1，表示已经不是二叉平衡树了。

代码如下：

int leftHeight = getHeight(node->left); // 左
    if (leftHeight == -1) return -1;
    int rightHeight = getHeight(node->right); // 右
    if (rightHeight == -1) return -1;
    
    int result;
    if (abs(leftHeight - rightHeight) > 1) {
          // 中
        result = -1;
    } else {
        
        result = 1 + max(leftHeight, rightHeight); // 以当前节点为根节点的树的最大高度
    }
    
    return result;

代码精简之后如下：

int leftHeight = getHeight(node->left);
    if (leftHeight == -1) return -1;
    int rightHeight = getHeight(node->right);
    if (rightHeight == -1) return -1;
    return abs(leftHeight - rightHeight) > 1 ? -1 : 1 + max(leftHeight, rightHeight);

此时递归的函数就已经写出了，这个递归的函数传入节点指针，返回以该节点为根节点的二叉树的高度，如果不是二叉平衡树，则返回-1。

getHeight整体代码如下：

int getHeight(TreeNode* node) {
        
        if (node == NULL) {
        
            return 0;
        }
        int leftHeight = getHeight(node->left);
        if (leftHeight == -1) return -1;
        int rightHeight = getHeight(node->right);
        if (rightHeight == -1) return -1;
        return abs(leftHeight - rightHeight) > 1 ? -1 : 1 + max(leftHeight, rightHeight);
    }

最后本题整体递归代码如下：

class Solution {
        
    public:
        // 返回以该节点为根节点的二叉树的高度，如果不是平衡二叉树了则返回-1
        int getHeight(TreeNode* node) {
        
            if (node == NULL) {
        
                return 0;
            }
            int leftHeight = getHeight(node->left);
            if (leftHeight == -1) return -1;
            int rightHeight = getHeight(node->right);
            if (rightHeight == -1) return -1;
            return abs(leftHeight - rightHeight) > 1 ? -1 : 1 + max(leftHeight, rightHeight);
        }
        bool isBalanced(TreeNode* root) {
        
            return getHeight(root) == -1 ? false : true;
        }
    };

## 3.2 迭代 ##

在 104.二叉树的最大深度 中我们使用层序遍历来求深度，但是就不能直接用层序遍历来求高度了，这就体现出求高度和求深度的不同。

本题的迭代方式可以先定义一个函数，专门用来求高度。

这个函数通过栈模拟的后序遍历找每一个节点的高度（其实是通过求传入节点为根节点的最大深度来求的高度）。

然后再用栈来模拟后序遍历，遍历每一个节点的时候，再去判断左右孩子的高度是否符合。

当然此题用迭代法，其实效率很低，因为没有很好的模拟回溯的过程，所以迭代法有很多重复的计算。

虽然理论上所有的递归都可以用迭代来实现，但是有的场景难度可能比较大。

**例如：都知道回溯法其实就是递归，但是很少人用迭代的方式去实现回溯算法！**

因为对于回溯算法已经是非常复杂的递归了，如果再用迭代的话，就是自己给自己找麻烦，效率也并不一定高。

# 4. 总结 #

通过本题可以了解求二叉树深度 和 二叉树高度的差异，求深度适合用前序遍历，而求高度适合用后序遍历。

本题迭代法其实有点复杂，大家可以有一个思路，也不一定说非要写出来。

但是递归方式是一定要掌握的！

# 5. 具体代码实现 #

## 5.1 递归法 ##

public boolean isBalanced(TreeNode root){
        
        return getHeight(root) != -1;
    }
    
    private int getHeight(TreeNode root){
        
        if(root == null){
        
            return 0;
        }
        int leftHeight = getHeight(root.left);
        if(leftHeight == -1){
        
            return -1;
        }
        int rightHeight = getHeight(root.right);
        if(rightHeight == -1){
        
            return -1;
        }
        // 左右子树高度差大于1，return -1表示已经不是平衡树了
        if(Math.abs(leftHeight - rightHeight) > 1){
        
            return -1;
        }
        return Math.max(leftHeight, rightHeight) + 1;
    }

## 5.2 迭代法 ##

/**
     * 迭代法，效率较低，计算高度时会重复遍历
     * 时间复杂度：O(n^2)
     * @param root
     * @return
     */
    public boolean isBalanced2(TreeNode root){
        
        if(root == null){
        
            return true;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode pre = null;
        while(root!=null || !stack.isEmpty()){
        
            while(root != null){
        
                stack.push(root);
                root = root.left;
            }
            TreeNode inNode = stack.peek();
            // 右节点为null或已经遍历过
            if (inNode.right == null || inNode.right == pre) {
        
                // 比较左右子树的高度差，输出
                if (Math.abs(getHeight2(inNode.left) - getHeight2(inNode.right)) > 1) {
        
                    return false;
                }
                stack.pop();
                pre = inNode;
                root = null;// 当前结点下，没有要遍历的结点了
            } else {
        
                root = inNode.right;// 右结点还没遍历，遍历右结点
            }
        }
        return true;
    }
    
    /**
     * 层序遍历，求结点的高度
     * @param root
     * @return
     */
    public int getHeight2(TreeNode root){
        
        if(root == null){
        
            return 0;
        }
        Deque<TreeNode> deque = new LinkedList<>();
        deque.offer(root);
        int depth = 0;
        while(!deque.isEmpty()){
        
            int size = deque.size();
            depth++;
            for(int i = 0;i < size; i++){
        
                TreeNode poll = deque.poll();
                if(poll.left != null){
        
                    deque.offer(poll.left);
                }
                if(poll.right != null){
        
                    deque.offer(poll.right);
                }
            }
        }
        return depth;
    }

## 5.3 优化迭代法 ##

// 110.平衡二叉树 - 优化迭代法
    /**
     * 优化迭代法，针对暴力迭代法的getHeight方法做优化，利用TreeNode.val来保存当前结点的高度，这样就不会有重复遍历
     * 获取高度算法时间复杂度可以降到O(1)，总的时间复杂度降为O(n)。
     * 时间复杂度：O(n)
     */
    public boolean isBalanced3(TreeNode root){
        
        if(root == null){
        
            return true;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode pre = null;
        while(root != null || !stack.isEmpty()){
        
            while(root != null){
        
                stack.push(root);
                root = root.left;
            }
            TreeNode inNode = stack.peek();
            // 右结点为null或已经遍历过
            if(inNode.right == null || inNode.right == pre){
        
                // 输出
                if(Math.abs(getHeight3(inNode.left) - getHeight3(inNode.right)) > 1){
        
                    return false;
                }
                stack.pop();
                pre = inNode;
                root = null;// 当前结点下，没有要遍历的结点了
            } else{
        
                root = inNode.right; // 右结点还没遍历，遍历右结点
            }
        }
        return true;
    }
    
    /**
     * 求结点的高度
     */
    public int getHeight3(TreeNode root) {
        
        if (root == null) {
        
            return 0;
        }
        int leftHeight = root.left != null ? root.left.val : 0;
        int rightHeight = root.right != null ? root.right.val : 0;
        int height = Math.max(leftHeight, rightHeight) + 1;
        root.val = height;// 用TreeNode.val来保存当前结点的高度
        return height;
    }

**参考资料**：[代码随想录-110.平衡二叉树][-110. 1]

[-110.]: https://leetcode.cn/problems/balanced-binary-tree/
[9d3310f3b63a4139b3cead2801c8c259.png]: https://img-blog.csdnimg.cn/9d3310f3b63a4139b3cead2801c8c259.png
[fe0240273b8646da89be1872c40a27ea.png]: https://img-blog.csdnimg.cn/fe0240273b8646da89be1872c40a27ea.png
[104.]: https://blog.csdn.net/qq_46130027/article/details/132796050
[2411bf4bcb4944b89184fd4c99dd7286.png]: https://img-blog.csdnimg.cn/2411bf4bcb4944b89184fd4c99dd7286.png
[-110. 1]: https://programmercarl.com/0110.%E5%B9%B3%E8%A1%A1%E4%BA%8C%E5%8F%89%E6%A0%91.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE