leetcode 剑指 Offer 68 - II. 二叉树的最近公共祖先

   声明:本站部分内容来自互联网,如若本站内容侵犯了原著者的合法权益,可联系我们进行处理。

24

文章目录

    • 题目要求
    • 解题思路
      • 方法一
      • 方法二

题目要求

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为:“对于有根树 T 的两个结点 p、q,最近公共祖先表示为一个结点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)。”

例如,给定如下二叉树: root = [3,5,1,6,2,0,8,null,null,7,4]

解题思路

方法一

  1. 遍历整棵树,用字典储存每个节点的父节点。
  2. 利用字典得到p节点的路径并保存。
  3. 从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