C++ avoid two recursion by returning the height of each subtree, and pass over current height to parent level.


  • 0
    Y

    Note the height is passed as a reference, so you can reuse it in invoking function.
    Or, you may define your function to return a tuple like tuple<bool, int> of status and height.

    class Solution {
    public:
        bool isBalanced(TreeNode* root) {
            if(!root)
                return 1;
            int h;
            return imp(root, h);
        }
        
        bool imp(TreeNode* root, int& height){
            if(!root){
                height =0;
                return 1;
            }
            int left= 0;
             bool status = imp(root->left, left);
             if(!status)
                return 0;
            int right=0;    
            bool s2 = imp(root->right, right);
            if(!s2)
                return 0;
            if(std::abs(left-right) <=1){
                height = left >right ? left +1  :right + 1;
                return 1;
            }else
                return 0;
        }
    };
    
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.