Lowest Common Ancestor of a Binary Search Tree Runtime Error


  • 0
    K
    /**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    class Solution {
    public:
        unordered_map <TreeNode*, TreeNode*> parent;
        unordered_map <TreeNode*, int> depth;
        unordered_map <TreeNode*, unordered_map<int, TreeNode*> > lcaTable;
    
        void bfs(TreeNode* root, TreeNode* p, TreeNode* q) {
            queue <TreeNode*> Q;
            Q.push(root);
            parent[root] = root;
            depth[root] = 0;
            lcaTable[root][0] = root;
            bool foundP = false, foundQ = false;
            while(!Q.empty()) {
                TreeNode* node = Q.front();
                Q.pop();
                TreeNode* left = node->left;
                TreeNode* right = node->right;
                if(left) {
                    if(left->val == p->val) {
                        foundP = true;
                    } else if(left->val == q->val) {
                        foundQ = true;
                    }
                    lcaTable[left][0] = node;
                    depth[left] = depth[node] + 1;
                    parent[left] = node;
                    Q.push(left);
                }
                if(right) {
                    if(right->val == p->val) {
                        foundP = true;
                    } else if(right->val == q->val) {
                        foundQ = true;
                    }
                    lcaTable[right][0] = node;
                    depth[right] = depth[node] + 1;
                    parent[right] = node;
                    Q.push(right);
                }
                if(foundP and foundQ) {
                    break;
                }
            }
        }
    
        void lcaInit(TreeNode* p) {
            for(int i = 1; (1 << i) < depth[p]; ++i) {
                lcaTable[p][i] = lcaTable[lcaTable[p][i - 1]][i - 1];
            }
        }
    
        int logDepth(TreeNode* p) {
            int log = 1;
            while(true) {
                int next = log + 1;
                if((1 << next) > depth[p]) break;
                log++;
            }
            return log;
        }
    
        TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
            if(!root or !p or !q) return nullptr;
            bfs(root, p, q);
            lcaInit(p);
            lcaInit(q);
    
            if(depth[p] < depth[q]) swap(p, q);
    
            int log = logDepth(p);
    
            for(int i = log - 1; i >= 0; --i) {
                if(depth[p] - (1 << i) >= depth[q]) {
                    p = lcaTable[p][i];
                }
            }
    
            if(p->val == q->val) return p;
    
            log = logDepth(p);
            for(int i = log - 1; i >= 0; --i) {
                if(lcaTable[p][i] != lcaTable[q][i]) {
                    p = lcaTable[p][i], q = lcaTable[q][i];
                }
            }
            cout << parent[p] << " " << parent[p]->val << endl; // for debug purpose
            return parent[p];
        }
    };
    

    Above code yield runtime error for following input:

    [45,30,46,10,36,null,49,8,24,34,42,48,null,4,9,14,25,31,35,41,43,47,null,0,6,null,null,11,20,null,28,null,33,null,null,37,null,null,44,null,null,null,1,5,7,null,12,19,21,26,29,32,null,null,38,null,null,null,3,null,null,null,null,null,13,18,null,null,22,null,27,null,null,null,null,null,39,2,null,null,null,15,null,null,23,null,null,null,40,null,null,null,16,null,null,null,null,null,17], node with value 47, node with value 15
    

    But when I printed parent[p] and parent[p]->val just before returning, it showed valid output: 37

    Why runtime error? Thanks in advance.


  • 0
    N
    // I recorded the parents of both p and q.
    // Then I compare their parents.
    /**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    class Solution {
    public:
        TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        	vector<TreeNode*> v1, v2;
        	dfs(root,p,v1);
        	dfs(root,q,v2);
        	for(int i=0;i<v1.size();i++){
        		for(int j=0;j<v2.size();j++){
        			if(v1[i]==v2[j]){
        				return v1[i];
    				}
    			}
    		}
    		return root;
        }
        bool dfs(TreeNode* root, TreeNode* p, vector<TreeNode*> &v){
        	if(root==p){
        		v.push_back(root);
        		return true;
        	}
        	if(root==NULL)return false;
        	bool s1=dfs(root->left,p,v);
        	bool s2=dfs(root->right,p,v);
        	if(s1||s2)v.push_back(root);
        	return s1||s2;
    	}
    };

  • 0
    K

    I didn't ask for source code. Thanks!


Log in to reply
 

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