听朋友说去小米二面的题是找到二叉树中两个节点的最低共同祖先,搜了下leetcode,发现果然有这道题,leetcode中有两道,一道是在BST中寻找,而另一道是在普通的二叉树中。听说剑指offer中的题要求是一般的树,难度更大。

先就做这两道题吧,总体感觉很容易,基本上提交一次就accepted了,哎,突然想去面试下,说不定还可以去小米= =!

其实我觉得寻找最低公共祖先,你得摸清情况,比如在BST中,有这么几种情况,当要搜寻的节点比p,q值都大,说明共同祖先应该在这个节点左侧,反之则在右侧,然后如果在这两个值中间,那就说明这个节点就是最低公共祖先了。

如果是普通的二叉树,递归的进行查找,首先来看查看的这个节点如果是p或者q,则返回,然后去这个节点左侧找,直到为None或者找到p,接下来去这个节点的右侧找,直到找到None或者找到p,如果一个找到p,一个找到q,则说明这个节点就是最低公共祖先。如果有一个是None,说明一个p在q上面,或者q在p上面。

总之吧,就是递归地处理这些情况,考虑清楚就好了。

BST

原题链接

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
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def lowestCommonAncestor(self, root, p, q):
"""
:type root: TreeNode
:type p: TreeNode
:type q: TreeNode
:rtype: TreeNode
"""
if not root:
return
if p == q:
return p
a, b = sorted([p.val, q.val])
def find_ancestor(node):
if not node:
return
elif node.val > a and node.val > b:
return find_ancestor(node.left)
elif node.val < a and node.val < b:
return find_ancestor(node.right)
else:
return node
res = find_ancestor(root)
return res

Binary Tree

原题链接

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
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def lowestCommonAncestor(self, root, p, q):
"""
:type root: TreeNode
:type p: TreeNode
:type q: TreeNode
:rtype: TreeNode
"""
def find_ancestor(node):
if not node:
return
if node == p or node == q:
return node
l = find_ancestor(node.left)
r = find_ancestor(node.right)
if l and r:
return node
return l or r
return find_ancestor(root)