Leetcode 二叉树专辑

230. Kth Smallest Element in a BST

中序遍历的非递归写法:

  • 指针指向 root
  • while root 反复将 root 指向 root.left,并将 node 缓存到 stack 里,直到 none 为止
  • 遇到 none 之后,从 stack 中 pop 出最后一个元素,也就是最左侧元素,push 进结果里,然后 root 跳到 right 节点,再重复上面的步骤
  • 跳出条件的 root 为空(已经到了最左侧)且 stack 为空(无法 pop 出新节点)
class Solution:
    def kthSmallest(self, root: TreeNode, k: int) -> int:
        s = []
        result = []
        
        while s or root:
            while root:
                s.append(root)
                root = root.left
            root = s.pop()
            result.append(root.val)
            if len(result) == k:
                return result[-1]
            root = root.right