Share my c solution


  • 0
    E
    bool helper(struct TreeNode *root,struct TreeNode *temp);
    struct TreeNode* lowestCommonAncestor(struct TreeNode* root, struct TreeNode* p, struct TreeNode* q) {
        if(p==NULL||q==NULL) return NULL;
        struct TreeNode *stack[10000];
        struct TreeNode *ret=NULL;
        struct TreeNode *first=NULL;
        int size=0;
        while(root||size){
            if(root!=NULL){
                stack[size]=root;
                size++;
                if(root==p||root==q){
                    first=root;
                    break;
                }
                root=root->left;
                stack[size-1]->left=NULL;
            }else if(size>0){
                if(stack[size-1]->right!=NULL){
                    root=stack[size-1]->right;
                    stack[size-1]->right=NULL;
                }else{
                    size--;
                }
            }
        }
        if(first==NULL) return NULL;
        if(first==p){
            for(int i=size-1;i>=0;i--) if(helper(stack[i],q)) return stack[i];
        }else if(first==q){
            for(int i=size-1;i>=0;i--) if(helper(stack[i],p)) return stack[i];
        }
        return ret;
    }
    bool helper(struct TreeNode *root,struct TreeNode *temp){
        if(root==NULL) return false;
        if(root==temp) return true;
        return helper(root->left,temp)||helper(root->right,temp);
    }

  • 0
    Z

    Can you really do if(p == root)? Would that check the equality of 2 nodes?


  • 0
    Z

    Can you really do if(p == root)? Would that check the equality of 2 nodes?


  • 0
    E

    yeah, actually i tried checking the value of the two nodes before, the result was wrong, there could be two nodes in the same tree with same value......I guess both of the p and q nodes in this problem are from the tree.


Log in to reply
 

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