题目描述:
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先. 百度百科中最近公共祖先的定义为:" 对于有根树 T 的两个结点 p,q, 最近公共祖先表示为一个结点 x, 满足 x 是 p,q 的祖先且 x 的深度尽可能大 (一个节点也可以是它自己的祖先).
解法一: 自己的写法, 贼傻
- # 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 findPath(root,num,tmp,path):
- if not root:
- return
- if root.val == num.val:
- path.append(tmp + [root])
- return
- findPath(root.left,num,tmp+[root],path)
- findPath(root.right,num,tmp+[root],path)
- minn = min(p.val, q.val)
- maxn = max(p.val, q.val)
- p_path = []
- q_path = []
- findPath(root,p,[],p_path)
- findPath(root,q,[],q_path)
- p_path = p_path[0]#[::-1]
- q_path = q_path[0]#[::-1]
- lenm = min(len(p_path),len(q_path))
- for i in range(0,lenm):
- if p_path[i].val == q_path[i].val:
- res = p_path[i]
- return res
网上的写法
- # Definition for a binary tree node.
- # class TreeNode:
- # def __init__(self, x):
- # self.val = x
- # self.left = None
- # self.right = None
- class Solution:
- def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
- min_ = min(p.val,q.val)
- max_ = max(p.val,q.val)
- if not root:
- return
- if min_ <= root.val <= max_:
- return root
- else:
- l = self.lowestCommonAncestor(root.left, p, q)
- r = self.lowestCommonAncestor(root.right, p, q)
- if l:
- return l
- if r:
- return r
来源: http://www.bubuko.com/infodetail-3134695.html