数据结构：平衡二叉树（时间复杂度O(N)解法）_平衡二叉树各项操作时间复杂度

平衡二叉树：一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1

时间复杂度O（N^2）

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
int TreeHeight(struct TreeNode* root)
{
    if(root == NULL)
    return 0;
    int leftheight = TreeHeight(root->left);
    int rightheight = TreeHeight(root->right);
    return leftheight > rightheight ? leftheight+1 : rightheight+1;
}

bool isBalanced(struct TreeNode* root){
    if(root == NULL)
    return true;
    int leftheight = TreeHeight(root->left);
    int rightheight = TreeHeight(root->right);
    return abs(leftheight-rightheight) < 2 &&
        isBalanced(root->left) &&isBalanced(root->right);
    }
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

优化：时间复杂度O(N)解法

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     
1
2
3