Correctness error for duplicate nodes


  • 1
    U

    My code is failing for following input
    [37,-34,-48,null,-100,-100,48,null,null,null,null,-54,null,-71,-22,null,null,null,8]
    node with value -100
    node with value -71

    There are 2 nodes with value -100 and I don't understand which was passed as "p" to the program.

    /**
     * Lowest Common ancestor of a binary tree
     * 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:
    
        bool lineage(TreeNode *root, vector<TreeNode*>& ancestors, TreeNode *p) {
            if (root == NULL || p == NULL) {
                return false;
            }
            
            if (root->val == p->val) {
                return true;
            }
            
            bool found = (lineage(root->left, ancestors, p) || lineage(root->right, ancestors, p));
            if (found) {
                ancestors.push_back(root);
            }
            return found;
        }
        
        bool is_traceable(TreeNode *root, TreeNode *q) {
            if (root == NULL || q == NULL) {
                return false;
            }
            
            if (root->val == q->val) {
                return true;
            }
            return (is_traceable(root->left, q) || is_traceable(root->right, q));
        }
        
        TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
            vector<TreeNode*> ancestors;
            
            // Check if p or q are traceable from each other
            if (is_traceable(p, q)) {
                return p;
            }
            
            if (is_traceable(q, p)) {
                return q;
            }
            
            // Find all ancestors of p;
            bool result = lineage(root, ancestors, p);
            if (!result) {
                return NULL;
            }
            
            for (int i = 0; i < ancestors.size(); ++i) {
                // Check for every ancestor if q is traceable.
                if (is_traceable(ancestors[i], q)) {
                    return ancestors[i];
                }
            }
        }
    };

  • 1
    S

    try checking like root == p instead of root->val == q->val


Log in to reply
 

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