Topic describes

Input the root node of a binary tree to determine whether the tree is a balanced binary tree. A binary tree is a balanced binary tree if the depth difference between the left and right subtrees of any node is no more than 1.

Example 1:

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


    3
   / \
  9  20
    /  \
   15   7
Copy the code

Returns true.

Example 2:

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

       1
      / \
     2   2
    / \
   3   3
  / \
 4   4
Copy the code

Train of thought

A binary balanced tree and any of its subtrees have the property that the depth difference between the left and right subtrees is less than or equal to one. We use the method of sequential traversal to judge by the following logic:

  1. If the current node is empty, 0 is returned (through the leaf node);
  2. If the height of the left subtree of the current node is == -1, it indicates that the left subtree is unbalanced and -1 is directly returned. If the height of the right subtree of the current node is == -1, it indicates that the right subtree is unbalanced and -1 is directly returned.
  3. If the depth difference between the left subtree of the current node and the right subtree is less than or equal to one, return Max (left, right) + 1, that is, the depth of the current node.
  4. If the difference between the depth of the left subtree and the depth of the right subtree of the current node is more than one, and the depth is unbalanced, -1 is returned.

C + + code

class Solution {
public:
    bool isBalanced(TreeNode* root) {
        returndfs(root) ! =- 1;
    }
    int dfs(TreeNode* root){// DFS for post-traversal
        if(! root)//对应1.
            return 0;
        int left = dfs(root->left);
        if(left == - 1)return left;
        int right = dfs(root->right);
        if(right == - 1)return right;//对应2.
        if(abs(left - right) < 2)
            return max(left, right) + 1;//对应3.
        else
            return - 1;//对应4.}};Copy the code

This article is participating in the “Gold Digging march Campaign”, click to see the details of the campaign.