LintCode (88) Lowest Common Ancestor

Given the root and two nodes in a Binary Tree. Find the lowest common ancestor(LCA) of the two nodes.

The lowest common ancestor is the node with largest depth which is the ancestor of both nodes.

Have you met this question in a real interview? 

Yes

Example

For the following binary tree:

  4
 / \
3   7
   / \
  5   6

LCA(3, 5) = 4

LCA(5, 6) = 7

LCA(6, 7) = 7




经典的LCA啊。。。。common ancestor必然是往一个方向数只能数出一个来，因为另一个方向必有

一个。。。数孩子的时候用了divide and conquer...其他的就是用这个trick了，  经典问题，没有说的了。。。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40

/** * 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) { if (root==A || root==B) return root; int left=count(root->left, A, B); if (left==1 ) return root; if (left==0 ) return lowestCommonAncestor(root->right,A,B); if (left==2) return lowestCommonAncestor(root->left,A,B); } int count(TreeNode* root, TreeNode* A, TreeNode* B){ if (!root) return 0; int left=count(root->left, A, B); int right=count(root->right, A, B); return left+ right+int(root==A||root==B); } };