lintcode88. 最近公共祖先

￡神魔★判官ぃ 2023-07-03 10:40 20阅读 0赞

给定一棵二叉树，找到两个节点的最近公共父节点(LCA)。  
最近公共祖先是两个节点的公共的祖先节点且具有最大深度。

样例
    样例 1:
    
    输入：{
        1},1,1
    输出：1
    解释：
     二叉树如下（只有一个节点）:
             1
     LCA(1,1) = 1
    样例 2:
    
    输入：{
        4,3,7,#,#,5,6},3,5
    输出：4
    解释：
     二叉树如下:
    
          4
         / \
        3   7
           / \
          5   6
    			
     LCA(3, 5) = 4
    注意事项
    假设给出的两个节点都在树中存在

/**
     * 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:
        /*
         * @param root: The root of the binary search tree.
         * @param A: A TreeNode in a Binary.
         * @param B: A TreeNode in a Binary.
         * @return: Return the least common ancestor(LCA) of the two nodes.
         */
        TreeNode * lowestCommonAncestor(TreeNode * root, TreeNode * A, TreeNode * B) {
        
            // write your code here
            if(root==NULL)return NULL;
            bool ra=search(root->right,A);
            bool rb=search(root->right,B);
            bool la=search(root->left,A);
            bool lb=search(root->left,B);
            if(ra&&rb)return lowestCommonAncestor(root->right,A,B);
            else if(la&&lb) return lowestCommonAncestor(root->left,A,B);
            else return root;
        }
        bool search(TreeNode*root,TreeNode*A)
        {
        
            if(root==NULL)return false;
            if(root==A) return true;
            return search(root->left,A)||search(root->right,A);
        }
    };