110-平衡二叉树

LeetCode 110. Balanced Binary Tree

LeetCode-110

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 left and right subtrees of every node differ in height by no more than 1.

Example 1:

Input: root = [3,9,20,null,null,15,7]
Output: true

method: 递归

平衡二叉树：左子树和右子树的高度差的绝对值小于1

• 这里用-1表示不满足的情况
• 如果左右子树出现不满足的情况，就可以直接返回了
• 都满足的话就取左右子树的较大者加1作为当前节点的深度返回

int getDepth(TreeNode* root) {
    if (!root) return 0;
    int leftDepth = getDepth(root->left);
    if (leftDepth == -1) return -1;
    int rightDepth = getDepth(root->right);
    if (rightDepth == - 1) return -1;
    return abs(leftDepth - rightDepth) > 1 ? -1 : 1 + max(leftDepth, rightDepth);
}
bool isBalanced(TreeNode* root) {
    return getDepth(root) == -1 ? false : true;
}

时间复杂度：$O(n)$，因为是自底向上的遍历，所以每个节点最多被访问一次
空间复杂度：$O(n)$，递归调用的深度不会超过$n$层