跟着卡哥学算法Day 21：二叉树常见题目8

递归#

• 当前节点值小于 low，其左子树的所有节点值更小，都不在范围内，这时候递归处理右子树，并返回处理后的节点作为当前节点
• 当前节点值大于 high，其右子树的所有节点值更大，都不在范围内，递归处理左子树，并返回处理后的节点作为当前节点
• 当前节点值在 low 和 high 之间时，需要同时处理左右子树，并将处理后的节点作为当前节点的左右孩子

递归三部曲：

1. 明确递归函数的参数和返回值

   • 参数 1：当前节点
   • 参数 2：low
   • 参数 3：high
   • 返回值：处理后的节点

2. 明确终止条件

   • 当节点为 null 返回 null

3. 确定单层递归逻辑

   • node.val < low，左子树都小于 low，递归处理右子树

     1
     if (node.val < low) {
     2
       return trimBST(root.right, low, high)
     3
     }

   • node.val > high，右子树都大于 high，递归处理左子树

     1
     if (node.val > high) {
     2
       return trimBST(root.left, low, high)
     3
     }

   • 否则，node.val 在范围内，递归左右子树

     1
     node.left = trimBST(root.left, low, high)
     2
     node.right = trimBST(root.right, low, high)
     3
     return node

1
function trimBST(root, low, high) {
2
  if (!root) return null
3

4
  if (root.val < low) {
5
    return trimBST(root.right, low, high)
6
  }
7
  if (root.val > high) {
8
    return trimBST(root.left, low, high)
9
  }
10

11
  root.left = trimBST(root.left, low, high)
12
  root.right = trimBST(root.right, low, high)
13
  return root
14
}

迭代#

迭代方法通过队列遍历所有节点，逐步调整结构：

1. 调整根节点：找到第一个符合范围的节点作为新根。
2. 层序处理每个节点：
   • 处理左子节点：若左子节点的值小于 low，则用其右子树替换，直到符合条件。
   • 处理右子节点：若右子节点的值大于 high，则用其左子树替换，直到符合条件。

1
function trimBST(root, low, high) {
2
  // 1. 调整根节点
3
  while (root && (root.val < low || root.val > high)) {
4
    root = root.val < low ? root.right : root.left
5
  }
6
  if (!root) return null
7

8
  // 2. 层序遍历处理所有节点
9
  const queue = [root]
10
  while (queue.length) {
11
    const node = queue.shift()
12

13
    // 处理左子节点
14
    while (node.left && node.left.val < low) {
15
      node.left = node.left.right
16
    }
17
    if (node.left) queue.push(node.left)
18

19
    // 处理右子节点
20
    while (node.right && node.right.val > high) {
21
      node.right = node.right.left
22
    }
23
    if (node.right) queue.push(node.right)
24
  }
25

26
  return root
27
}

利用升序数组构造二叉搜索树#

不能随便选节点作为根，而是需要让左右子树的节点数尽可能接近，这样高度差才会小

如：[-10, -3, 0, 5, 9]

• 数字长度为奇数，中间元素为 0，作为根节点，左右各两个节点[-10, -3]

• 此时左右节点长度为偶数，根节点选择中间任何一个节点都可以

  1
  // 例如4个元素，索引是0到3
  2
  // 中间位置的计算是(0+3)/2=1.5
  3
  // Math.floor得到1，所以mid=1
  4
  // 或Math.ceil的话得到2
  5
  // 这两种取法都会导致不同的树结构，但都是平衡的

递归#

递归三部曲：

1. 确定递归函数的参数和返回值

   • 参数 1：有序数组
   • 参数 2：left 区间
   • 参数 3：right 区间
   • 返回值：树节点（用于构造中节点的左右孩子）

2. 确定终止条件

   当左区间 left>右区间 right 时，就是空节点

   1
   if (left > right) return null

3. 确定单层递归逻辑

   • 取中间节点 const mid = left + ((right - left) / 2)
   • 构造树节点 const root = new TreeNode(nums[mid])
   • 根据区间，继续构造左右子树

1
function sortedArrayToBST(nums) {
2
  const buildTree = (nums, left, right) => {
3
    if (left > right) return null
4

5
    const mid = Math.floor(left + (right - left) / 2)
6
    const root = new TreeNode(nums[mid])
7

8
    root.left = buildTree(nums, left, mid - 1)
9
    root.right = buildTree(nums, mid + 1, right)
10
    return root
11
  }
12

13
  return buildTree(nums, 0, nums.length - 1)
14
}

递归#

递归三部曲：

1. 确定递归函数的参数和返回值

   • 参数 1：根节点
   • 返回值：不需要

2. 确定终止条件

   遇到空节点终止，返回

   1
   if (!root) return

3. 确定单层递归逻辑

   • 右 -> 中 -> 左顺序
   • 中节点处理逻辑：root.val += sum

1
function convertBST(root) {
2
  let sum = 0
3
  const traverse = (root) => {
4
    if (!root) return
5

6
    root.right && traverse(root.right)
7
    sum += root.val
8
    root.val = sum
9
    root.left && traverse(root.left)
10
  }
11

12
  traverse(root)
13

14
  return root
15
}

迭代#

步骤解析：

• 栈模拟遍历：用栈实现反向中序遍历。
• 循环处理右子树：先将所有右子节点压入栈中，再逐个处理并转向左子树。

1
const convertBST = function (root) {
2
  let sum = 0
3
  let stack = []
4
  let curr = root
5

6
  while (curr || stack.length) {
7
    // 将当前节点的所有右子节点入栈
8
    while (curr) {
9
      stack.push(curr)
10
      curr = curr.right
11
    }
12
    curr = stack.pop() // 处理当前节点
13
    sum += curr.val
14
    curr.val = sum
15
    curr = curr.left // 转向左子树
16
  }
17
  return root
18
}