# [LeetCode 230] 通过栈迭代进行中序遍历

要说中序遍历,肯定是递归最简单。但是递归的问题就是不能在中间退出,所以为了性能,还是用栈来进行迭代比较好。整体来说思路还是比较简单的。

function kthSmallest(root: TreeNode | null, k: number): number {
  const stack: TreeNode[] = [];
  while (root || stack.length) {
    while (root) {
      stack.push(root);
      root = root.left;
    }
    root = stack.pop()!;
    if (--k) return root.val;
    root = root.right;
  }
  return -1;
}
最后更新于: 6/25/2020, 2:10:06 PM