LeetCode 110 Balanced Binary Tree | 平衡二叉树判断

题目来源：LeetCode: 110. Balanced Binary Tree

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
3
4
5
6
7
8
9
10
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
bool isBalanced(struct TreeNode* root) {
}

思路：根节点->左右子树高度->高度差是否大于1->返回True/False
首先想到肯定用递归来解决，一个函数计算高度，根据左右子树的高度差判定是否平衡二叉树。
哪里递归呢？计算高度的函数：某一个节点的高度=max(左子树高度,右子树高度)+1
递归过程中应判断子节点是否符合平衡二叉树要求，加入节点子树高度差大于1或为负数时高度返回-1，作为递归过程的判断。
临界条件：节点为null时，返回高度为0

ok, let’s do it~

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
// 110. Balanced Binary Tree
// LeetCode: https://leetcode.com/problems/balanced-binary-tree/
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
int getDepth(struct TreeNode* root) {
    if(root == NULL)
        return 0;
    int l = getDepth(root->left);
    int r = getDepth(root->right);
    if ( l<0 || r<0 || abs(l-r)>1 )
        return -1;
    return (l>r)?(l+1):(r+1);
}
bool isBalanced(struct TreeNode* root) {
    if(root == NULL)
        return true;
    int l = getDepth(root->left);
    int r = getDepth(root->right);
    if ( l<0 || r<0 || abs(l-r)>1 )
        return false;
    else
        return true;
}

226 / 226 test cases passed.

Status: Accepted

Runtime: 8 ms

Submitted: 0 minutes ago