Daily practice (28): balance binary tree

---

title: Practice every day （28）： Balanced binary trees

categories:[ The finger of the sword offer]

tags:[ Practice every day ]

date: 2022/03/01

---

Practice every day （28）： Balanced binary trees

Enter the root node of a binary tree , Judge whether the tree is a balanced binary tree . If the depth difference between the left and right subtrees of any node in a binary tree does not exceed 1, So it's a balanced binary tree .

Example 1:

Given binary tree [3,9,20,null,null,15,7]

 3
/ \
9  20
/  \
15   7

return true .

Example 2:

Given binary tree [1,2,2,3,3,null,null,4,4]

   1
  / \
 2   2
 / \
3   3
 / \
4   4

return false .

Limit ：

0 <= The number of nodes in a tree <= 10000

source ： Power button （LeetCode）

link ：https://leetcode-cn.com/probl...

Method 1 ： After the sequence traversal （DFS）

dfs Calculation ideas ：

• For empty nodes , Depth is 0
• The current depth is the maximum depth of the left and right subtrees +1, The valid case returns the depth directly
• Once the depth difference between the left and right subtrees is more than 1, Is considered invalid , return -1
• Once found, the return is -1, Go straight back to -1

bool isBalanced(TreeNode* root) {
    return (dfs(root) != -1);
}
int dfs(TreeNode* node) {
    if (node == nullptr) {
        return 0;
    }
    int left = dfs(node->left);
    if (left == -1) {
        return -1;
    }
    int right = dfs(node->right);
    if (right == -1) {
        return -1;
    }
    return abs(left - right) > 1 ? -1 : max(left, right) + 1;// The current depth is the maximum depth of the left and right subtrees +1,  The valid case returns the depth directly 
}

Method 2 ： The former sequence traversal

For the node currently traversed , First, calculate the height of the left and right subtrees , If the height difference between the left and right subtrees does not exceed 11, Then recursively traverse the left and right child nodes , And judge whether the left subtree and the right subtree are balanced . this

Is a top-down recursive process

int height(TreeNode* root) {
    if (root == nullptr) {
        return 0;
    }
    return max(height(root->left), height(root->right)) + 1;
}
bool isBalanced(TreeNode* root) {
    if (root == nullptr) {
        return true;
    }
    return abs(height(root->left) - height(root->right)) <= 1 && isBalanced(root->left) && isBalanced(root->right);
}