Leetcode 110. balanced binary tree

Leetcode 110. Balanced binary trees

subject

Given a binary tree , Determine if it's a highly balanced binary tree .

Ideas

• Specify the parameters and return values of recursive functions ： The parameter is the passed in node pointer , The return value is the height of the binary tree with this node as the root node
• Specify termination conditions ： Return when encountering empty node 0, Indicates that the height of the tree with the current node as the root node is 0
• Explicit single-layer recursive logic ： Judge the height difference between the left and right subtrees , If the difference is less than or equal to 1, Returns the height of the current binary tree

Code

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */
class Solution {
    
public:
//  Returns the height of the binary tree with this node as the root node 
    int getDepth(TreeNode *node)
    {
    
        if(node == NULL)
        {
    
            return 0;
        }
        int leftDepth = getDepth(node->left);
        if(leftDepth == -1)
        {
    
            return -1;//  It shows that the left subtree is no longer a balanced binary tree 
        }

        int rightDepth = getDepth(node->right);
        if(rightDepth == -1)
        {
    
            return -1;//  It shows that the right subtree is no longer a balanced binary tree 
        }
        return abs(leftDepth - rightDepth) > 1 ? -1 : 1 + max(leftDepth,rightDepth);
    }


    bool isBalanced(TreeNode* root) {
    
        return getDepth(root) == -1 ? false:true;
    }
};