LeetCode 110.平衡二叉树 (C++)

题目地址：力扣

平衡二叉树，指的就是每个节点的左右子树高度相差不超过1的树

解法1：从上往下

思路：首先需要知道左子树和右子树的高度，那么可以定义一个depth函数求高度，要求高度那么很显然是递归函数，从上向下找到最高的再返回上来。总的判断二叉树平衡又需要满足三个条件：

1、当前节点是平衡的

2、当前节点的左子树是平衡的

3、当前节点的右子树是平衡的

因此判断是否平衡的函数也是一个递归函数。

这种解法容易想到，但是有一个问题在于很多操作都重复求了同一个节点的高度，因此这种方法的时间复杂度较高。

class Solution {
public:
    // depth函数用于返回当前节点的深度
    int depth(TreeNode *root)
    {
        if (root == nullptr)
            return 0;
        else
            return max(depth(root->left), depth(root->right)) + 1;
    }
 
    
    bool isBalanced(TreeNode* root) {
        // 若当前节点为空，则必平衡
        if (root == nullptr)
            return true;
        // 若当前节点不为空，那么要验证三个东西
        // 1.当前节点是平衡的
        // 2.当前节点的左子树是平衡的
        // 3.当前节点的右子树是平衡的
        else
            return abs(depth(root->left) - depth(root->right) <= 1) && isBalanced(root->left) && isBalanced(root->right);
    }
};

解法2：从下往上

思路：从下往上判断，如果下面的某个节点不满足平衡二叉树的定义，那么这棵树必然不满足定义，因此我们需要从下往上找，那么这也决定了depth函数必然是递归的。

但是这个递归要做两件事情

1、如果左右子树都满足平衡，那么需要返回当前节点的最大深度给上一个节点

2、如果左右子树有一者不满足，就将不满足的信息一直传递给最外层的节点

class Solution {
public:
    int depth(TreeNode* root)
    {
        // 空节点高度为0
        if (root == nullptr)
            return 0; 
        // 左子树深度和右子树深度
        int leftDepth = depth(root->left);
        int rightDepth = depth(root->right);
 
        // 如果左右子树其一不满足平衡情况，则直接传递-1给上层
        if (leftDepth == -1 || rightDepth == -1)
            return -1;
        else
        // 左右子树满足，则判断当前节点是否满足平衡，若满足返回当前节点最大深度，不满足则返回-1
            if (abs(leftDepth - rightDepth) <= 1)
                return max(leftDepth, rightDepth) + 1;
            else
                return -1;
    }
    
    bool isBalanced(TreeNode* root) {
        // 只需要判断结果是否是-1即可
        if (depth(root) != -1)
            return true;
        else
            return false;
    }
};