寻找二叉树公共祖先结点递归实现

  

   

    

     

    
    

     

      /**
     
    
   

    

     

    
    

     

       * Definition for a binary tree node.
     
    
   

    

     

    
    

     

       * struct TreeNode {
     
    
   

    

     

    
    

     

       * int val;
     
    
   

    

     

    
    

     

       * TreeNode *left;
     
    
   

    

     

    
    

     

       * TreeNode *right;
     
    
   

    

     

    
    

     

       * TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     
    
   

    

     

    
    

     

       * };
     
    
   

    

     

    
    

     

       */
     
    
   

    

     

    
    

     

      /*寻找公共祖先结点LCA算法de思想：
     
    
   

    

     

    
    

     

      第零种情况：root为null时直接return
     
    
   

    

     

    
    

     

      第一种情况：如果p在左子树q在右子树或反之则root为LCA
     
    
   

    

     

    
    

     

      第二种情况：p和q均在左子树(LCA递归左子树)
     
    
   

    

     

    
    

     

      第三种情况：p和q均在右子树(LCA递归右子树)
     
    
   

    

     

    
    

     

      PS:最后return的right和left不会同时为NULL
     
    
   

    

     

    
    

     

      */
     
    
   

    

     

    
    

     

      class Solution {
     
    
   

    

     

    
    

     

      public:
     
    
   

    

     

    
    

     
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
     
    
   

    

     

    
    

     
        if(root==NULL||root==p||root==q) return root;
     
    
   

    

     

    
    

     

              TreeNode* left=lowestCommonAncestor(root->left,p,q);
     
    
   

    

     

    
    

     

              TreeNode* right=lowestCommonAncestor(root->right,p,q);
     
    
   

    

     

    
    

     
        if(left && right){
     
    
   

    

     

    
    

     
            return root; 
     
    
   

    

     

    
    

     

              }else{
     
    
   

    

     

    
    

     
            return left==NULL?right:left;
     
    
   

    

     

    
    

     

              }
     
    
   

    

     

    
    

     

          }
     
    
   

    

     

    
    

     
     
     
    
   

    

     

    
    

     

      };
     
    
  
 

文章来源: andyguo.blog.csdn.net，作者：山顶夕景，版权归原作者所有，如需转载，请联系作者。

原文链接：andyguo.blog.csdn.net/article/details/96555993