C++ non-recursive code with considering not both p and q are all in the tree (return NULL)


  • 0
    S

    C++

    class Solution {
    public:
        TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
            vector<TreeNode*> stack;
            TreeNode* node = root;
            TreeNode* lca = NULL;
            TreeNode* n1 = NULL;
            TreeNode* n2 = NULL;
            if(p->val < q->val)
            {
                n1 = p;
                n2 = q;
            }
            else
            {
                n1 = q;
                n2 = p;
            }
            while(node)
            {
                stack.push_back(node);
                if(node->val == n1->val)  // searching for the smaller one;
                {
                    lca = node;
                    break;
                }
                else if(node->val > n1->val)
                    node = node->left;
                else
                    node = node->right;
            }
            
            if(!lca) return NULL; // not found p in the tree
            
            while(stack.size() > 0)
            {
                lca = stack.back();
                stack.pop_back();
                node = lca;
                while(node)
                {
                    if(node->val == n2->val)
                        return lca;
                    else if (node->val > n2->val)
                        node = node->left;
                    else
                        node = node->right;
                }
            }
            return NULL;
            
        }
    };

Log in to reply
 

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