Leetcode 235 二叉搜索树的最低公共祖先

Question

给定二叉搜索树 (BST)，找到 BST 中两个给定节点的最低公共祖先 (LCA) 节点。

根据维基百科上LCA的定义：“最低公共祖先被定义在两个节点
p
和
q
之间，作为
T
中的最低节点，同时具有
p
和
q
作为后代（我们允许一个节点成为其自身的后代）。”

我的代码如下：


class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        ans = None

        def travel(root, p, q, ans):
            if not root: return
            temp=[]
            if root:
                temp.append(root.val)
            if root.right:
                temp.append(root.right.val)
            if root.left:
                temp.append(root.left.val)
            if p.val in temp and q.val in temp:
                ans = root
            if ans:
                return ans
            travel(root.left, p, q, ans)
            travel(root.right, p, q, ans)

        return travel(root, p, q, ans)

这个测试用例失败了：

输入：
root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
输出：
2
解释： 节点 2 和 4 的 LCA 是 2，因为根据 LCA 定义，节点可以是其自身的后代。

有人可以解释为什么我的代码对于上述给定的输入返回

None

吗？

当我尝试

print(ans)

时，它显示了正确的答案。我的错误是什么？

Answer 1

有几个问题：

首先回答“为什么我的代码返回 null ...当我尝试打印（ans）时它显示了正确的答案”：这是因为当您从递归调用返回时，您丢失了
```
ans
```
的值。丢失的原因有两个：
1. 这些递归调用可能会返回您需要的值，但您的代码会忽略它们返回的内容。然后调用者将返回
```
None
```
  ，即使递归调用可能返回了您需要的值。您想做类似
```
ans = travel(root.left, p, q, ans)
```
  的事情，然后检查
```
ans
```
  是什么...等等。
2. 您似乎认为对
```
ans
```
  的赋值也会更新调用者作为（参数）变量的
```
ans
```
  。但事实并非如此。
```
travel
```
  的每次执行都有自己的
```
ans
```
  局部变量，并且分配给一个变量不会更新另一个变量。将
```
ans
```
  作为参数传递没有帮助。您不妨删除该参数。

temp

最多会收集三个值，它们位于同一个父子“家庭”中：当p

和

q

时，您只会检测到共同的祖先（在解决第一个问题之后）要么是直系亲子关系，要么是直系兄弟姐妹。如果

p

和

q

 相距较远，它们将永远不会被收集在同一个

temp

 列表中，因此您将找不到任何共同的父级。例如，当您输入以下内容时，您的代码将失败：

[1,null,2,null,3]

和

p=1

和

q=3

。

您的代码没有使用给定二叉树是二叉
search树这一事实。除非您使用此属性，否则您将无法找到足够有效的解决方案来通过测试。

所以你的方法必须彻底改变。以下是您可以使用的算法的描述：

如果

p

和

q

的值都

小于给定根的值，那么你知道p

和

q

都在该根下面的左子树中（BST）财产）。那么

root

 就不是最近的共同祖先，因为

root.left

 肯定是

更接近。您可以以 root.left

 作为新根递归地解决问题。

类似地，如果
p
```
和
```
q
```
的值都
```
大于根的值，则可以递归到root.right
```
。
```

如果上述条件都不成立，那么我们就会遇到这样的情况：

p

和

q

之一是根的左子树，另一个是右子树。还有一种边界情况，其中

p

或

q

是 根本身。但在所有这些情况下 root

 都是一个共同祖先，我们知道

root.left

和

root.right

 都不是共同祖先，因此当前根是我们想要返回的节点。

这是一个剧透实现：

def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode': if root: if root.val > max(p.val, q.val): return self.lowestCommonAncestor(root.left, p, q) if root.val < min(p.val, q.val): return self.lowestCommonAncestor(root.right, p, q) return root

Leetcode 235 二叉搜索树的最低公共祖先

问题描述投票：0回答：1

1个回答

最新问题

Leetcode 235 二叉搜索树的最低公共祖先

问题描述 投票：0回答：1

1个回答

最新问题

问题描述投票：0回答：1