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.
Example
Method 1: Transform it to the problem of finding the first common node of two linked lists.
4
/ \
3 7
/ \
5 6
For 3 and 5, the LCA is 4.
For 5 and 6, the LCA is 7.
For 6 and 7, the LCA is 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: bool hasNode(vector<TreeNode*> &rec,TreeNode *node, TreeNode *target) { if(!node) return false; if(node == target || hasNode(rec, node->left, target) || hasNode(rec, node->right, target)) { rec.push_back(node); return true; } return false; } TreeNode *lowestCommonAncestor(TreeNode *root, TreeNode *A, TreeNode *B) { if(!root) return NULL; vector<TreeNode*> recA; hasNode(recA, root, A); vector<TreeNode*> recB; hasNode(recB, root, B); int lenA = recA.size(), lenB = recB.size(); if(0 == lenA || 0 == lenB) return NULL; int i = lenA-1, j = lenB-1; while(i>=0 && j>=0 && recA[i] == recB[j]) { i--; j--; } return recA[i+1]; } };Method 2: Very neat
class Solution { public: TreeNode *lowestCommonAncestor(TreeNode *root, TreeNode *A, TreeNode *B) { if(!root) return NULL; if(root == A || root == B) return root; TreeNode *left = lowestCommonAncestor(root->left, A, B); TreeNode *right = lowestCommonAncestor(root->right, A, B); if(left && right) return root; return left?left:right; } };