LeetCode110平衡二叉树

Posted on | | Visitors:
Words count in article: 362 字 | Reading time ≈ 2 分

题目链接

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

题解

  • 递归解法
  • 平衡二叉树定义：一个二叉树每个结点的左右两个子树的高度差的绝对值不超过1
  • 递归函数返回值：如果平衡则返回该树的高度，空树则返回0，不平衡（左右子树不平衡或该结点不平衡）则返回-1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
// Problem: LeetCode 110
// URL: https://leetcode-cn.com/problems/balanced-binary-tree/description/
// Tags: Tree DFS
// Difficulty: Easy

#include <iostream>
#include <algorithm>
using namespace std;

struct TreeNode{
    TreeNode* left;
    TreeNode* right;
    int val;
    TreeNode(int x):val(x), left(nullptr), right(nullptr){}
};

class Solution{
private:
    int recursion(TreeNode* root){//若该树平衡则返回其高度，不平衡则返回-1
        // 空树深度为0，也算平衡树
        if(root==nullptr)
            return 0;

        // 计算左子树和右子树深度
        int left=recursion(root->left);
        int right=recursion(root->right);

        // 若子树不平衡，则父树也不平衡(平衡二叉树定义：一个二叉树每个结点的左右两个子树的高度差的绝对值不超过1)
        if(left<0||right<0)
            return -1;
        
        // 左右子树平衡，则判断该树是否平衡
        if (abs(left-right)<=1)
            return max(left,right)+1;
        else
            return -1;
    }

public:
    bool isBalanced(TreeNode* root){
        return recursion(root)>=0;
    }
};

作者：@臭咸鱼

转载请注明出处：https://www.cnblogs.com/chouxianyu/

欢迎讨论和交流!