Leetcode: Balanced Binary Tree

傷城~ 2022-08-07 04:35 187阅读 0赞

题目：  
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.

题目分析：  
平衡二叉树：（1）要么为空，要么左右子树的深度差值不超过1；（2）左右两个子树都是一棵平衡二叉树，即子树也都要都满足条件（1）。显然这是一个递归的定义。

C++参考示例代码：

/** * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */
    class Solution
    {
    private:
        bool checkBalanced(TreeNode *node, int &depth)
        {
            if (node == NULL)
            {
                depth = 0;
                return true;
            }
    
            int leftDepth, rightDepth;
            bool leftBalanced = checkBalanced(node->left, leftDepth);
            bool rightBalanced = checkBalanced(node->right, rightDepth);
    
            depth = max(leftDepth, rightDepth) + 1;//求以node为根节点的深度
            return leftBalanced && rightBalanced && abs(leftDepth - rightDepth) <= 1;
        }
    public:
        bool isBalanced(TreeNode *root)
        {
            int depth;
            return checkBalanced(root, depth);
        }
    };

发表评论取消回复

表情：

评论列表（有 0 条评论，187人围观）

还没有评论，来说两句吧...

相关阅读

相关 LeetCode - Easy - 110. Balanced Binary Tree

Topic Tree Depth-first Search Recursion Description [https://leetcode.co

小灰灰/ 2022年12月28日 09:05/ 0 赞/ 154 阅读

相关 LeetCode - Medium - 1382. Balance a Binary Search Tree

Topic Divide and Conquer Binary Search Tree Depth-First Search Description

╰+哭是因爲堅強的太久メ/ 2022年10月11日 13:37/ 0 赞/ 189 阅读

相关 LeetCode110 - Balanced Binary Tree

\[Q\] Given a binary tree, determine if it is height-balanced. For this problem, a hei

浅浅的花香味﹌/ 2022年08月07日 08:55/ 0 赞/ 44 阅读

相关 Leetcode: Balanced Binary Tree

题目： Given a binary tree, determine if it is height-balanced. For this problem, a heig

傷城~/ 2022年08月07日 04:35/ 0 赞/ 188 阅读

相关 LeetCode110-Balanced Binary Tree

LeetCode 110 : Balanced Binary Tree Given a binary tree, determine if it is height-bala

落日映苍穹つ/ 2022年08月04日 12:48/ 0 赞/ 28 阅读

相关 LeetCode-Balanced Binary Tree

Given a binary tree, determine if it is height-balanced. For this problem, a height-bal

痛定思痛。/ 2022年08月04日 00:57/ 0 赞/ 19 阅读

相关 LeetCode110—Balanced Binary Tree

LeetCode110—Balanced Binary Tree 原题 > Given a binary tree, determine if it is heig

偏执的太偏执、/ 2022年07月28日 05:12/ 0 赞/ 170 阅读

相关 [leetcode]: 110. Balanced Binary Tree

1.题目 Given a binary tree, determine if it is height-balanced. For this problem, a he

爱被打了一巴掌/ 2022年06月15日 05:20/ 0 赞/ 197 阅读

相关 110. Balanced Binary Tree

题目描述： Given a binary tree, determine if it is height-balanced. For this problem, a hei

阳光穿透心脏的1/2处/ 2022年06月08日 14:59/ 0 赞/ 199 阅读

相关 110. Balanced Binary Tree

Given a binary tree, determine if it is height-balanced. For this problem, a height-bal

系统管理员/ 2022年03月26日 08:59/ 0 赞/ 203 阅读