LeetCode110. Balanced Binary Tree（二叉树 / 搜索）

Easy
Accepted：298,683
Submissions：738,371

Given a binary tree, determine if it is height-balanced.

For this problem, a height-balanced binary tree is defined as:

a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

Example 1:

Given the following tree [3,9,20,null,null,15,7]:

Return true.

Example 2:

Given the following tree [1,2,2,3,3,null,null,4,4]:

Return false.

链接

https://leetcode.com/problems/balanced-binary-tree

题意

给定一颗二叉树，判断它是否是高度平衡的。一棵高度平衡的二叉树是指每个结点的两个子树的深度之差不会超过1。

题解

之前有一道题：LeetCode104. Maximum Depth of Binary Tree（二叉树 / 搜索），求二叉树的最大深度，我们是采用递归的做法分别求左子树和右子树的深度然后取max，所以对于这道题，我们可以在求左右子树的深度后加一个判断，看是否超过1。

时间复杂度的话，因为每个结点都要访问一次，所以平均时间复杂度为$O(n)$。

代码

Runtime: 16 ms, faster than 99.63% of C++ online submissions for Balanced Binary Tree.
Memory Usage: 17.2 MB, less than 83.65% of C++ online submissions for Balanced Binary Tree.

class Solution {
public:
    bool isBalanced(TreeNode* root) {
        solve(root);
        return flag;
    }

private:
    bool flag = true;
    int solve(TreeNode* root)
    {
        if (root == NULL)
            return 0;
        int leftDepth = solve(root->left);
        int rightDepth = solve(root->right);
        if (abs(leftDepth - rightDepth) > 1) // 高度差超过1
        {
            flag = false;
            return 0;
        }
        return max(leftDepth, rightDepth) + 1;
    }
};

感觉我这种写法不是很好。

The end.
2019年3月15日星期五