230. 二叉搜索树（BST）中第 K 小的元素 🟨

题目

LeetCode 中等

给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 个最小元素（从 1 开始计数）。

示例 1：
输入：root = [3,1,4,null,2], k = 1
输出：1

示例 2：
输入：root = [5,3,6,2,4,null,null,1], k = 3
输出：3

题解

使用中序遍历

方法：递归

递归 O(N) O(N)

class TreeNode {
  constructor(val, left = null, right = null) {
    this.val = val
    this.left = left
    this.right = right
  }
}

function kthSmallest(root, k) {
  let res = null

  let inOrderTraverseNode = function (node) {
    console.log('♻️ node', node?.val, 'k', k)
    if (node !== null && k > 0) {
      console.log('if 内 node', node.val)

      inOrderTraverseNode(node.left)

      console.log('---- node', node.val, 'k', k)

      if (--k === 0) {
        res = node.val
        console.log('🎉 find node', node.val)
        return
      }

      console.log('????? node', node.val, 'k', k)

      inOrderTraverseNode(node.right)
    }
  }
  inOrderTraverseNode(root)

  return res
}

const tree = new TreeNode(5)
tree.left = new TreeNode(3, new TreeNode(2, new TreeNode(1)), new TreeNode(4))
tree.right = new TreeNode(6)

console.log('🌰', JSON.stringify(kthSmallest(tree, 4)))

执行结果

♻️ node 5 k 4
if 内 node 5
♻️ node 3 k 4
if 内 node 3
♻️ node 2 k 4
if 内 node 2
♻️ node 1 k 4
if 内 node 1
♻️ node undefined k 4
---- node 1 k 4
????? node 1 k 3
♻️ node undefined k 3
---- node 2 k 3
????? node 2 k 2
♻️ node undefined k 2
---- node 3 k 2
????? node 3 k 1
♻️ node 4 k 1
if 内 node 4
♻️ node undefined k 1
---- node 4 k 1
🎉 find node 4
---- node 5 k 0
????? node 5 k -1
♻️ node 6 k -1
🌰 4

方法：迭代

迭代 O(H + k) O(H)

class TreeNode {
  constructor(val, left = null, right = null) {
    this.val = val
    this.left = left
    this.right = right
  }
}

function kthSmallest(root, k) {
  const stack = []
  while (root != null || stack.length) {
    console.log('-------------')
    console.log('root', root?.val, 'k', k)
    console.log(stack.map(i => i.val))

    while (root != null) {
      stack.push(root)
      root = root.left

      console.log(stack.map(i => i.val))
    }

    root = stack.pop()
    --k
    if (k === 0) {
      break
    }

    console.log('root pop', root.val)

    root = root.right

    console.log('root right', root?.val)
  }
  return +root.val
}

const tree = new TreeNode(5)
tree.left = new TreeNode(3, new TreeNode(2, new TreeNode(1)), new TreeNode(4))
tree.right = new TreeNode(6)

console.log('🌰', JSON.stringify(kthSmallest(tree, 4)))

执行结果

-------------
root 5 k 4
[]
[5]
[5,3]
[5,3,2]
[5,3,2,1]
root pop 1
root right undefined
-------------
root undefined k 3
[5,3,2]
root pop 2
root right undefined
-------------
root undefined k 2
[5,3]
root pop 3
root right 4
-------------
root 4 k 1
[5]
[5,4]
🌰 4

本页目录