lintcode - 요즘 공공조상 - 88

1553 단어
두 갈래 트리를 지정하여 두 노드의 가장 가까운 공통 부모 노드(LCA)를 찾습니다.
최근 공공 조상은 두 노드의 공공 조상 노드이며 최대 깊이를 가지고 있다.
예제
밑에 있는 이 두 갈래 나무에 대해
 4 / \ 3 7 / \ 5 6 

LCA(3, 5) = 4
LCA(5, 6) = 7
LCA(6, 7) = 7
/**
 * Definition of TreeNode:
 * class TreeNode {
 * public:
 *     int val;
 *     TreeNode *left, *right;
 *     TreeNode(int val) {
 *         this->val = val;
 *         this->left = this->right = NULL;
 *     }
 * }
 */

class Solution {
public:
   
    TreeNode *lowestCommonAncestor(TreeNode *root, TreeNode *A, TreeNode *B) {
        if(!root)                 
            return NULL; 
        if(root==A)      
            return A;
        if(root==B)
            return B;
       
        TreeNode *L=lowestCommonAncestor(root->left,A,B);
        TreeNode *R=lowestCommonAncestor(root->right,A,B);
    
        if(L&&R)  // A B root , root
            return root;

/*      
        if(!L&&!R)        // A B root , NULL
            return NULL;  
        if(L&&!R)       // A B , A, A 
             return L;           
        if(!L&&R)
             return R;
                      //   
*/
        return L?L:R;      
    }
};


좋은 웹페이지 즐겨찾기