题目描述

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

示例 1:

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

  3
 / \
9  20
  /  \
 15   7

返回 $true$ 。

示例 2:

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

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

返回 $false$ 。

限制：

• $0 <= 树的结点个数 <= 10000$

注意：本题与主站 110 题相同：https://leetcode-cn.com/problems/balanced-binary-tree/

---

算法 1

(DFS,递归) $O(n)$

这道题目其实就是在求二叉树中的每个节点最大深度（高度）的过程中判断以当前节点为根的树是否为二叉平衡树。

定义一个全局答案，首先假设是平衡二叉树，递归后序遍历二叉树，遍历的过程中如果遇到不是平衡二叉树的节点，说明整棵二叉树就不是平衡二叉树。

时间复杂度

二叉树的每个节点只会被遍历一次，所以时间复杂度为 $O(n)$。

空间复杂度

$O(logn)$，最坏情况下 $O(n)$。

C++ 代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool ans = true;

    int dfs(TreeNode* root) {
        if (!root) return 0;
        int lh = dfs(root->left), rh = dfs(root->right);
        if (abs(lh - rh) > 1) ans = false;
        return max(lh, rh) + 1;
    }

    bool isBalanced(TreeNode* root) {
        dfs(root);
        return ans;
    }
};

算法 2

(BFS,迭代) $O(n^2)$

首先使用层序遍历 BFS 写一个求节点高度的函数。

迭代法前序遍历二叉树，对于每个节点判断它的左子树和右子树的高度之差绝对值是否大于 1，如果大于 1 说明不是平衡二叉树，否则当所有节点遍历完成后，说明该树是一棵平衡二叉树。

时间复杂度

求二叉树的高度所需的时间为 $O(n)$，每个节点都需要求一次高度，所以时间复杂度为 $O(n^2)$。

空间复杂度

最坏情况下每次求二叉树的高度所需系统栈空间为 $O(n)$。

C++ 代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int getDepth(TreeNode* root) {
        queue<TreeNode*> q;
        if (root) q.push(root);

        int depth = 0;
        while (q.size()) {
            depth ++ ;
            int sz = q.size();
            while (sz -- ) {
                auto t = q.front();
                q.pop();
                if (t->left) q.push(t->left);
                if (t->right) q.push(t->right);
            }
        }
        return depth;
    }

    bool isBalanced(TreeNode* root) {
        stack<TreeNode*> stk;
        if (root) stk.push(root);
        while (stk.size()) {
            auto t = stk.top();
            stk.pop();

            if (abs(getDepth(t->left) - getDepth(t->right)) > 1) return false;

            if (t->right) stk.push(t->right);
            if (t->left) stk.push(t->left);
        }
        return true;
    }
};