Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.
According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).”
_______3______
/ ___5__ ___1__
/ \ / 6 _2 0 8
/ 7 4
For example, the lowest common ancestor (LCA) of nodes 5 and 1 is 3. Another example is LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.
DFS:
1. Base Case: 一般是找到符合条件的
2. recursive: 调用本身
3. Judgement: 一般是排除不符合条件的
1 /** 2 * Definition for a binary tree node. 3 * struct TreeNode { 4 * int val; 5 * TreeNode *left; 6 * TreeNode *right; 7 * TreeNode(int x) : val(x), left(NULL), right(NULL) {} 8 * }; 9 */ 10 class Solution { 11 public: 12 TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { 13 //在二叉树中来搜索p和q，然后从路径中找到最后一个相同的节点即为父节点，我们可以用递归来实现 14 //base case 15 if(!root || root == p || root == q) return root; 16 //recursive 17 TreeNode* left = lowestCommonAncestor(root -> left, p, q); 18 TreeNode* right = lowestCommonAncestor(root -> right, p, q); 19 //judgement 20 if(left && right) return root;//如果一个在左子树 一个在右子树 return root 21 return left ? left : right;//如果left不为空 return left 反之返回right 22 } 23 };
236. Lowest Common Ancestor of a Binary Tree
原文：http://www.cnblogs.com/93scarlett/p/6362001.html