A straightforward, explanatory iterative approach in C++


  • 0
    Q
    class Solution {
    public:
        //static bool balance=true;
        bool isBalanced(TreeNode *root) {
            // depth(root)=max(depth(left),depth(right))+1;
            // if(!root) depth=0;
            //depth(root);
            if(!root) return true;
            return depth(root);
        }
        
        int depth(TreeNode *root) { // return depth or 0 if unbalanced
            vector<TreeNode *> tstn; //stack of unprocessed nodes with at least one child
            bool processed=false, unbalanced=false;
            TreeNode *top;
            int tmp, dep;
            vector<int> depstn; // stack of recently calculated unused depth
            do { 
                if(processed) {
                    top=tstn.back();
                    if(root==top->left) {
                        if(top->right) { // top->left==root, top->right!=NULL
                            depstn.push_back(dep);
                            root=top->right;
                            processed=false;
                        }
                        else { // top->left==root, top->right==NULL. processed remain true
                            if(dep>1) { return 0; }
                            dep=2;
                            root=top;
                            tstn.pop_back();
                        }
                    }
                    else { 
                        if(!top->left){ // top->left==NULL, top->right==root. processed remain true
                            if(dep>1) { return 0; }
                            dep=2;
                            root=top;
                            tstn.pop_back();
                        }
                        else { // depth(top->left) is in depstn, top->right==root. processed remain true
                            tmp=depstn.back(); // only here depstn was popped
                            if(tmp-dep>1 || tmp-dep<-1) { return 0; }
                            depstn.pop_back();
                            root=tstn.back();
                            tstn.pop_back();
                            dep=(tmp>dep)?(tmp+1):(dep+1);
                        }
                    }
                }
                else { 
                    if(root->left) { // case 3, 2, root->left!=NULL
                            tstn.push_back(root);
                            root=root->left;
                    }
                    else {
                        if(root->right) { // case 1, root->left==NULL, root->right!=NULL
                            tstn.push_back(root);
                            root=root->right;
                        }
                        else { // case 0, root->left==NULL, root->right==NULL
                            dep=1;
                            processed=true;
                        }
                    }
                }
            } while(!tstn.empty()); // only nonNULL one was pushed on to stack tstn
            return dep;
        }
    };

Log in to reply
 

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