网络工程师职业分析_北京公司网站如何制作_如何快速推广一个app_郑州关键词排名外包

题目

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

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

示例 1：

输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出：3
解释：节点 5 和节点 1 的最近公共祖先是节点 3 。

示例 2：

输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出：5
解释：节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。

示例 3：
输入：root = [1,2], p = 1, q = 2
输出：1

提示：

• 树中节点数目在范围 [2, 105] 内。
• -109 <= Node.val <= 109
• 所有 Node.val 互不相同 。
• p != q
• p 和 q 均存在于给定的二叉树中。

题目链接

我的思路

• 思路1：用一个函数判断当前节点是不是两个节点的公共祖先，如果是，记录下来，然后判断它的左右子树是不是，最后返回的是最小的
• 思路2：层序遍历后得到一个数组，用数组来做，算p和q间下标较大的，找它的父节点的下标和另一个节点的下标比较是否相等，如果不相等，再算p和q间下标较大的那个的父节点

思路不足：

• 尝试用思路2做，但是发现存在问题：层序遍历会把null省略，导致有的能过有的不能过

题解思路

最近公共祖先定义： 设节点 root 为节点 p,q 的某公共祖先，若其左子节点 root.left 和右子节点 root.right 都不是 p,q 的公共祖先，则称 root 是 “最近的公共祖先” 。

根据以上定义，则只可能为以下情况之一：

• 如果 p 和 q 都在root的左子树中，那么root的左子树中会找到它们的最近公共祖先
• 如果 p 和 q 都在root的右子树中，那么root的右子树中会找到它们的最近公共祖先
• 如果一个在左子树，一个在右子树，那么root就是它们的最近公共祖先

因此，考虑通过递归对二叉树进行先序遍历，当遇到节点 p 或 q 时返回。从底至顶回溯，当节点 p,q 在节点 root 的异侧时，节点 root 即为最近公共祖先，则向上返回 root 。

递归：

• 递归左子节点，返回值记为 left
• 递归右子节点，返回值记为 right
  返回值：
  根据 left 和 right ，可展开为四种情况；
  

参考代码

class Solution:def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:if not root or root == p or root == q: return rootleft = self.lowestCommonAncestor(root.left, p, q)right = self.lowestCommonAncestor(root.right, p, q)if not left and not right: return # 1.if not left: return right # 3.if not right: return left # 4.return root # 2. if left and right

Q&A

1. 为什么当前节点是空节点 / p / q 时返回当前节点？
   • 如果当前节点root为空，那么它不可能是p和q的祖先
   • 由于我们要找的是最低公共祖先，如果其中一个节点就是当前节点，那么当前节点就是最低的公共祖先，因此返回root。