Beats 90%+ C++ Solution


  • 0
    E
    class Solution {
    public:
       
        void DFS(TreeNode* root, int depth, int &res){
            if(root){
                res=max(res,depth);
                if(root->left) DFS(root->left,depth+1,res);
                if(root->right) DFS(root->right,depth+1,res);
            }else{
                return;
            }
        }
        
        void judge(TreeNode* root,bool& flag){
            int leftDepth=0;
            int rightDepth=0;
            int leftMax=0;
            int rightMax=0;
            
            if(root->left) DFS(root->left,leftDepth+1,leftMax);     // DFS traversal the child nodes of current root
            if(root->right) DFS(root->right,rightDepth+1,rightMax);
            
            if(leftMax-rightMax>1 || leftMax-rightMax<-1){
                flag=false;
            }else{
                if(root->left) judge(root->left,flag);      // see if all the child nodes of current root are height-balanced 
                if(root->right) judge(root->right,flag);
            }
        }
        
        bool isBalanced(TreeNode* root) {
            if(root==NULL){
                return true;
            }
            bool flag=true;
            
            judge(root,flag);
           
            return flag;
        }
    };
    

Log in to reply
 

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