C Soulution


  • 0

    After the sequence traverses the tree, if

    • The current layer or the left subtree or right subtree finds p, and can not find q, return (-1);
      The current layer or the left subtree or the right sub tree to find q, and can not find p, return (1);
      The current layer or left subtree or right subtree can not find p can not find q, return (0);
      The current or left subtree or right subtree to find p, also find q, the global variable return_node set to the current node, and return (0), in order to deceive all the upper nodes, so that the upper node no longer Return_node to modify;

    Whether the current or left subtree or right subtree finds p, q is indicated by p_find_flag and q_find_flag.

    /**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     struct TreeNode *left;
     *     struct TreeNode *right;
     * };
     */
    struct TreeNode *return_node=NULL;
    int traversal(struct TreeNode* root, struct TreeNode* p, struct TreeNode* q)
    {
        if (root!=NULL)
        {
            int p_find_flag=0,q_find_flag=0;
            int left_flag=0,right_flag=0;
            
            left_flag=traversal(root->left,p,q);
            right_flag=traversal(root->right,p,q);
            
            if (root==p||left_flag==-1||right_flag==-1)
                p_find_flag=1;
            if (root==q||left_flag==1||right_flag==1)
                q_find_flag=1;
                
            if (p_find_flag==1&&q_find_flag==1)
            {
                return_node=root;
                return(0);
            }
            else if (p_find_flag==1)
                return(-1);
            else if (q_find_flag==1)
                return(1);
            else
                return(0);
        }
        else
            return(0);
    }
    struct TreeNode* lowestCommonAncestor(struct TreeNode* root, struct TreeNode* p, struct TreeNode* q) 
    {
        return_node==NULL;
        traversal(root,p,q);
        return(return_node);
    }
    

Log in to reply
 

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