为什么在BST中的LeetCode Kth Smallest Element中使用curr=curr.right

Question

所以我在解决LeetCode问题https://leetcode.com/problems/kth-smallest-element-in-a-bst/

这个问题的解决方案是

class Solution:
def kthSmallest(self, root: TreeNode, k: int) -> int:
stack = []
curr = root
while stack or curr:
while curr:
stack.append(curr)
curr = curr.left
curr = stack.pop()
k -= 1
if k == 0:
return curr.val
curr = curr.right

我不明白的一件事是为什么我们使用

curr=curr.right

在最后一行中，它的重要性是什么？

Answer 1

此解决方案按顺序遍历树。以下是需要最后一条声明的原因：

• 如果没有它，唯一可能的导航将是向左，因为这样就没有代码访问节点的右子级。

• 如果没有它，循环的下一次迭代将把从堆栈中弹出的同一节点推回到堆栈上，循环后它将再次弹出。这意味着pop调用将始终弹出相同的节点。唯一可能的返回值是具有最小值的节点。

• 将节点放在堆栈上的含义是：；我们现在要向左移动，但请提醒我稍后实际访问此节点，然后向右移动"。当一个节点被从堆栈中弹出时，时间已经到来：我们访问它(通过减少k的值(，然后向右移动，这样该节点的右侧子树也会被访问。