文章目录
- 题目要求
- 解题思路
- 方法一
- 方法二
题目要求
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为:“对于有根树 T 的两个结点 p、q,最近公共祖先表示为一个结点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)。”
例如,给定如下二叉树: root = [3,5,1,6,2,0,8,null,null,7,4]
解题思路
方法一
- 遍历整棵树,用字典储存每个节点的父节点。
- 利用字典得到p节点的路径并保存。
- 从q节点向根节点开始检查,当有某个节点在p节点的路径中时,此节点即为最近的公共节点。
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = Noneclass Solution(object):def lowestCommonAncestor(self, root, p, q):""":type root: TreeNode:type p: TreeNode:type q: TreeNode:rtype: TreeNode"""# 遍历整棵树def recursive(node):if not node:returnif node.left:dic[node.left] = noderecursive(node.left)if node.right:dic[node.right] = noderecursive(node.right)# 遍历整棵树dic = {}dic[root] = Nonerecursive(root)# 得到p节点的路径node = pp_path = [node]while node:p_path.append(dic[node])node = dic[node]# 利用q结点路径找到最近公共节点node = qwhile node:if node in p_path:res = nodebreaknode = dic[node]return res
方法二
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = Noneclass Solution(object):def lowestCommonAncestor(self, root, p, q):""":type root: TreeNode:type p: TreeNode:type q: TreeNode:rtype: TreeNode"""# 结点为空,返回空。if not root: return None# 递归left = self.lowestCommonAncestor(root.left, p, q)right = self.lowestCommonAncestor(root.right, p, q)# 若root等于p或q结点的一个,那么直接返回root。if root == q or root == p:return root# 在root不为p或q中一个时,且root无子节点,则返回空。if not left and not right:return None# 有left则返回left,有right则返回right。elif not left and right:return rightelif left and not right:return left# 当初次left和right都有值返回时,证明root即为最近公共祖先,返回之。else:return root










