给定一棵二叉树，找到两个节点的最近公共父节点(LCA)。

最近公共祖先是两个节点的公共的祖先节点且具有最大深度。

注意事项

假设给出的两个节点都在树中存在

样例

对于下面这棵二叉树

LCA(3, 5) = 4

LCA(5, 6) = 7

LCA(6, 7) = 7

标签

LintCode 版权所有 领英 二叉树 脸书

code

/** * 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 and B: two nodes 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        TreeNode * ancestor = NULL;        if(root==NULL || A==NULL || B==NULL)            return ancestor;        vector
    
      pathA, pathB;        searchTree(root, A, pathA);        searchTree(root, B, pathB);        int sizeA=pathA.size(), sizeB=pathB.size();        int size = sizeA>sizeB ? sizeB : sizeA, i=0;        bool find = false;        for(i=0; i
     
       &path) {        if(root==NULL || node==NULL) {              return false;          }        path.push_back(root);        //  找到了        if(root->val == node->val) {              return true;          }        if(root->left != NULL) {              if(searchTree(root->left, node, path)) {                  return true;              }          }          if(root->right != NULL) {              if(searchTree(root->right, node, path)) {                  return true;              }          }        //回溯        path.pop_back();         return false;      }};