题目描述：
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.
题目大意：
给定一棵二叉树，寻找其中两个给定节点的最近公共祖先（LCA）。
根据维基百科对LCA的定义：“节点v与w的最近公共祖先是树T上同时拥有v与w作为后继的最低节点（我们允许将一个节点当做其本身的后继）”
例如，题目描述的样例中，节点5和1的最近公共祖先（LCA）是3。另一个例子，节点5和4的LCA是5，因为根据LCA的定义，一个节点可以是其本身的后继。
解题思路：
迭代法：
后序遍历二叉树，得到从根节点到目标节点的“路径”，两条路径公共部分的末尾节点即为LCA
Python代码：
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
# @param {TreeNode} root
# @param {TreeNode} p
# @param {TreeNode} q
# @return {TreeNode}
def lowestCommonAncestor(self, root, p, q):
pathP, pathQ = self.findPath(root, p), self.findPath(root, q)
lenP, lenQ = len(pathP), len(pathQ)
ans, x = None, 0
while x < min(lenP, lenQ) and pathP[x] == pathQ[x]:
ans, x = pathP[x], x + 1
return ans
def findPath(self, root, target):
stack = []
lastVisit = None
while stack or root:
if root:
stack.append(root)
root = root.left
else:
peek = stack[-1]
if peek.right and lastVisit != peek.right:
root = peek.right
else:
if peek == target:
return stack
lastVisit = stack.pop()
root = None
return stack
递归法：
参考LeetCode Discuss
链接地址：https://leetcode.com/discuss/45386/4-lines-c-java-python-ruby
如果当前节点为空或者与目标节点之一相同，则返回当前节点
递归寻找p和q在左右子树中的位置
如果p和q分别位于root的左右两侧，则root为它们的LCA，否则为左子树或者右子树
C++代码：
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if (!root || root == p || root == q) return root;
TreeNode* left = lowestCommonAncestor(root->left, p, q);
TreeNode* right = lowestCommonAncestor(root->right, p, q);
return !left ? right : !right ? left : root;
}
本文链接：http://bookshadow.com/weblog/2015/07/13/leetcode-lowest-common-ancestor-binary-tree/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。
捐赠书影博客
