6-236. Lowest Common Ancestor of a Binary Tree

题目描述：

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 p?and q?as the lowest node in T that has both p?and q?as descendants (where we allow?a node to be a descendant of itself).”

Given the following binary tree:? root =?[3,5,1,6,2,8,null,7,4]

?

Example 1:

Input: root = [3,4],p = 5,q = 1
Output: 3
Explanation: The LCA of nodes  and  is 
513.

Example 2:

Input: root = [3,q = 4
Output: 5
Explanation: The LCA of nodes  and  is,since a node can be a descendant of itself according to the LCA definition.
545

?

Note:

• All of the nodes‘ values will be unique.
• p and q are different and both values will?exist in the binary tree.

他山之石：

 1 # Definition for a binary tree node.
 2 # class TreeNode(object):
 3 #     def __init__(self,x):
 4 #         self.val = x
 5 #         self.left = None
 6 #         self.right = None
 7 
 8 class Solution(object):
 9     def lowestCommonAncestor(self,root,p,q):
10         """
11         :type root: TreeNode
12         :type p: TreeNode
13         :type q: TreeNode
14         :rtype: TreeNode
15         """
16         # Stack for tree traversal
17         stack = [root]
18         # Dictionary for parent pointers
19         parent = {root: None}
20         # Iterate until we find both the nodes p and q
21         while p not in parent or q not in parent:
22 
23             node = stack.pop()
24 
25             # While traversing the tree,keep saving the parent pointers.
26             if node.left:
27                 parent[node.left] = node
28                 stack.append(node.left)
29             if node.right:
30                 parent[node.right] = node
31                 stack.append(node.right)
32 
33         # Ancestors set() for node p.
34         ancestors = set()
35 
36         # Process all ancestors for node p using parent pointers.
37         while p:
38             ancestors.add(p)
39             p = parent[p]
40 
41         # The first ancestor of q which appears in
42         # p‘s ancestor set() is their lowest common ancestor.
43         while q not in ancestors:
44             q = parent[q]
45         return q

?

分析：

Python的pop()函数用于移除列表中的一个元素（默认最后一个元素），并返回该元素的值。

stack在代码中是一个动态数组，最初stack=[TreeNode(3)]（以下直接以数字表示对应位置的树节点）。parent最初只是一个空的树节点。

第一个while循环相当于是对原二叉树的一个遍历，在遍历的过程中，parent树在不断生长，直到在parent树中检测到了节点p和q的存在，循环结束。

假如我们要寻找的两个节点是6和8，则parent树的生长过程如下：

最初stack=[3]，用pop()方法将3弹出，检测它的左右子节点是否存在，若存在（此时左子节点为5，右子节点为1），则将左右子节点按照先左后右的顺序存入stack中。

在第一轮循环结束时，stack = [5,1]。

parent树为：

? ? 3

? /? ? ?

5? ? ? ? 1

接下来进入第二轮循环，将stack的最后一个元素（即1）pop出来，以同样的方法，检查它的左右子节点是否存在，若存在（此时左为0，右为8），则再次将左右子节点按照先左后右的顺序存入stack中。

在第二轮循环结束时，stack = [5,8]。

parent树为：

? ? ? ? ? ? ? 3

? ? ? ? ? /? ? ? ? ?

? ? ?5? ? ? ? ? ? ? ? ?1

? ? ? ? ? ? ? ? ? ? ? /? ? ?

? ? ? ? ? ? ? ? ? ?0? ? ? ? 8

在第三轮循环结束时（在该轮循环中，只有pop，没有append），stack = [5,0]。

parent树为：

? ? ? ? ? ? ? 3

? ? ? ? ? /? ? ? ? ?

? ? ?5? ? ? ? ? ? ? ? ?1

? ? ? ? ? ? ? ? ? ? ? /? ? ?

? ? ? ? ? ? ? ? ? ?0? ? ? ? 8

在第四轮循环结束时（在该轮循环中，依然只有pop，没有append），stack = [5]。

parent树为：

? ? ? ? ? ? ? 3

? ? ? ? ? /? ? ? ? ?

? ? ?5? ? ? ? ? ? ? ? ?1

? ? ? ? ? ? ? ? ? ? ? /? ? ?

? ? ? ? ? ? ? ? ? ?0? ? ? ? 8

在第五轮循环结束时，stack = [6,2]。

parent树为：

? ? ? ? ? ? ? 3

? ? ? ? ? /? ? ? ? ?

? ? ?5? ? ? ? ? ? ? ? ?1

? ?/? ? ? ? ? ? ? ? ?/? ? ?

6? ? ? ?2? ? ? ? ?0? ? ? ? 8

此时，在parent中恰好能够同时检测到6和8，循环结束。

程序中的第二个while循环