剑指offer 55-2. 平衡二叉树

题目描述

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

示例 1:

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

返回 true 。

示例 2:

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

返回 false 。

限制：

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

题解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;
    }
};

Java 代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    boolean ans = true;
    
    public boolean isBalanced(TreeNode root) {
        dfs(root);
        return ans;
    }
    
    private int dfs(TreeNode root) {
        if (root == null) return 0;
        int lh = dfs(root.left), rh = dfs(root.right);
        if (Math.abs(lh - rh) > 1) ans = false;
        return Math.max(lh, rh) + 1;
    }
}

Python 代码

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def isBalanced(self, root: TreeNode) -> bool:
        self.ans = True
        
        def dfs(root):
            if not root:
                return 0
            lh = dfs(root.left)
            rh = dfs(root.right)
            if abs(lh - rh) > 1:
                self.ans = False
            return max(lh, rh) + 1
        
        dfs(root)
        return self.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;
    }
};

Java 代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isBalanced(TreeNode root) {
        return isBalancedWithDepth(root) != -1;
    }
    
    private int isBalancedWithDepth(TreeNode root) {
        if (root == null) return 0;
        
        int leftDepth = isBalancedWithDepth(root.left);
        if (leftDepth == -1) return -1;
        
        int rightDepth = isBalancedWithDepth(root.right);
        if (rightDepth == -1) return -1;
        
        if (Math.abs(leftDepth - rightDepth) > 1) return -1;
        
        return Math.max(leftDepth, rightDepth) + 1;
    }
}

Python 代码

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def isBalanced(self, root: TreeNode) -> bool:
        return self.isBalancedWithDepth(root) != -1
    
    def isBalancedWithDepth(self, root: TreeNode) -> int:
        if not root:
            return 0
        
        leftDepth = self.isBalancedWithDepth(root.left)
        if leftDepth == -1:
            return -1
        
        rightDepth = self.isBalancedWithDepth(root.right)
        if rightDepth == -1:
            return -1
        
        if abs(leftDepth - rightDepth) > 1:
            return -1
        
        return max(leftDepth, rightDepth) + 1

本文由读者提供，Github地址：https://github.com/tonngw

点击面试手册，获取本站面试手册PDF完整版

上一篇：剑指offer 55-1. 二叉树的深度

下一篇：剑指offer 56-1. 数组中数字出现的次数