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


  • 5
    S

    Non-recursive implement, return NULL if p, q or both are not in the three.

    C++

    class Solution {
    public:
        TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
            vector<TreeNode*> left_stack;
            vector<TreeNode*> right_stack;
            TreeNode* node = root;
            TreeNode* lca = NULL;
            while(node)
            {
                if(node == p || node == q)
                    if(lca == NULL)
                        lca = node;
                    else
                        return lca;
                left_stack.push_back(node);
                node = node->left;
            }
            while(left_stack.size() > 0)
            {
                node = left_stack.back();
                if(node->right == NULL)
                {
                    left_stack.pop_back();
                    if(node->left != NULL && node->left == lca)
                        lca = node;
                    continue;
                }
                if(right_stack.size() > 0 && node == right_stack.back())
                {
                    left_stack.pop_back();
                    right_stack.pop_back();
                    if(lca != NULL && (node->left == lca || node->right == lca))
                        lca = node;
                    continue;
                }
                if(lca != NULL && (node->left == lca || node->right == lca))
                    lca = node;
                right_stack.push_back(node);
                node = node->right;
                while(node)
                {
                    if(node == p || node == q)
                        if(lca == NULL)
                            lca = node;
                        else
                            return lca;
                    left_stack.push_back(node);
                    node = node->left;
                }
            }
            return NULL;
        }
    };

  • 0
    A

    Nice, thanks. I wanted to comment how most of solutions here are implemented with recursion, in which the base case (and further code) looks like this:

    if(root == NULL){
        return NULL;
    }
    if(root == p || root == q)
    {
        return root;
    }
    
    TreeNode *left = LDA(root->left,p, q);
    TreeNode *right = LDA(root->right,p,q);
    
    if(left && right) return root;
    return left ? left : right;
    

    According to my understanding, this means that if the LDA for a tree is one of the input nodes itself (either p or q), its subtree will never be explored. Instead, LDA function will just return either p or q, and it wont work for cases when either p or q are not present.

    Leetcode should add test cases when either p or q are not present in the three.

    Feel free to correct me if I am wrong.


Log in to reply
 

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