[Jianzhi offer] 55 - ii balanced binary tree

The finger of the sword Offer 55 - II. Balanced binary trees

subject

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 .

Ideas

  First, define a function to calculate the height of nodes , Then traverse according to the preorder of the binary tree , 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 1, Recursively traverse the left and right child nodes respectively , And judge whether the left and right subtrees are balanced .

Code

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */
class Solution {
    
public:
    int height(TreeNode* root)
    {
    
            if(root == NULL)
        {
    
            return 0;
        }
        else
        {
    
            //  Calculate the height of the binary tree 
            return max(height(root->left),height(root->right)) + 1;
        }
    }

    bool isBalanced(TreeNode* root) 
    {
    
        if(root == NULL)
        {
    
            return true;
        }
        else
        {
    
            return abs(height(root->left) - height(root->right)) <= 1 && isBalanced(root->left) && isBalanced(root->right);
        }
    }
};