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

题目描述#

给定一个不含重复元素的整数数组。一个以此数组构建的最大二叉树定义如下：

• 二叉树的根是数组中的最大元素。
• 左子树是通过数组中最大值左边部分构造出的最大二叉树。
• 右子树是通过数组中最大值右边部分构造出的最大二叉树。

通过给定的数组构建最大二叉树，并且输出这个树的根节点。

示例 ：

输入：[3, 2, 1, 6, 0, 5]

1
// 输出 树根节点
2
//       6
3
//      / \
4
//     3   5
5
//     \   /
6
//     2  0
7
//     \
8
//     1

解题思路#

• 关键：构造二叉树一定是前序遍历，先有根节点，递归构造左右子树

递归三部曲：

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

   • 参数 1：传入的数组
   • 返回值：根节点

2. 明确终止条件

   • 数组长度为 1 时，就是叶子节点，直接构造叶子节点并返回

3. 确定单层递归逻辑

   • 找最大值和对应下标，值用来构造根节点，下标用来分割数组（左右子树）

     1
     let max = nums[0]
     2
     let maxIndex = 0
     3
     for (let i = 1; i < nums.length; i++) {
     4
       if (nums[i] > max) {
     5
         max = nums[i]
     6
         maxIndex = i
     7
       }
     8
     }
     9
     const root = new TreeNode(max)

   • 分割数组

   • 用左区间构造左子树

     1
     root.left = constructMaximumBinaryTree(nums.slice(0, maxIndex))

   • 用右区间构造右子树

     1
     root.right = constructMaximumBinaryTree(nums.slice(maxIndex + 1))

1
function constructMaximumBinaryTree(nums) {
2
  if (!nums.length) return null
3

4
  const max = num[0]
5
  const maxIndex = 0
6
  for (let i = i; i < nums.length; i++) {
7
    if (nums[i] > max) {
8
      max = nums[i]
9
      maxIndex = i
10
    }
11
  }
12

13
  const root = new TreeNode(max)
14
  root.left = constructMaximumBinaryTree(nums.slice(0, maxIndex))
15
  root.right = constructMaximumBinaryTree(nums.slice(maxIndex + 1))
16

17
  return root
18
}

题目描述#

给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。

你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为 NULL 的节点将直接作为新二叉树的节点。

示例:

1
//     Tree 1                     Tree 2
2
//       1                         2
3
//      / \                       / \
4
//     3  2                      1   3
5
//    /                           \   \
6
//   5                            4    7
7

8
// 合并后
9
//     3
10
//    / \
11
//   4  5
12
//  /\   \
13
// 5 4   7

解题思路#

采用前序遍历最直观，与遍历一个树的逻辑一样

1
function mergeTrees(root1, root2) {
2
  if (!root1) return root2
3
  if (!root2) return root1
4

5
  root1.val += root2.val
6
  root1.left = mergeTrees(root1.left, root2.left)
7
  root1.right = mergeTrees(root1.right, root2.right)
8

9
  return root1
10
}

1
function mergeTrees(root1, root2) {
2
  if (!root1) return root2
3
  if (!root2) return root1
4

5
  const queue = [root1, root2]
6
  while (queue.length) {
7
    const node1 = queue.shift()
8
    const node2 = queue.shift()
9

10
    node1.val += node2.val
11

12
    if (node1.left && node2.left) {
13
      queue.push(node1.left)
14
      queue.push(node2.left)
15
    }
16
    if (node1.right && node2.right) {
17
      queue.push(node1.right)
18
      queue.push(node2.right)
19
    }
20
    if (!node1.left && node2.left) {
21
      node1.left = node2.left
22
    }
23
    if (!node1.right && node2.right) {
24
      node1.right = node2.right
25
    }
26
  }
27
  return root1
28
}

题目描述#

给定二叉搜索树（BST）的根节点和一个值。 你需要在 BST 中找到节点值等于给定值的节点。 返回以该节点为根的子树。 如果节点不存在，则返回 NULL。

示例:

1
// 给定二叉搜索树:
2
//       4
3
//      / \
4
//     2  7
5
//    / \
6
//   1  3
7
// 和值：2
8

9
// 返回
10
//     2
11
//    / \
12
//   1  3

解题思路#

二叉搜索树：根节点比左子树所有节点的值都大、比右子树所有节点的值都小，同时左右子树都是二叉搜索树

1
function searchBST(root, val) {
2
  if (!root || root.val === val) return root
3

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

1
function searchBST(root, val) {
2
  while (root) {
3
    if (root.val === val) return root
4

5
    if (root.val > val) {
6
      root = root.left
7
    }
8
    if (root.val < val) {
9
      root = root.right
10
    }
11
  }
12
  return root
13
}

题目描述#

给定一个二叉树，判断其是否是一个有效的二叉搜索树。

假设一个二叉搜索树具有如下特征：

• 节点的左子树只包含小于当前节点的数。
• 节点的右子树只包含大于当前节点的数。
• 所有左子树和右子树自身必须也是二叉搜索树。

1
//       2
2
//      / \
3
//     1  3
4
// 输出 true

解题思路#

常见错误：只比较每个节点与其左右节点的关系，没有考虑全局上节点的关系，如：某个右子树的左节点可能比父节点小，同时比根节点小

需要一个区间[min, max]来确定当前节点值是否在这个区间

代码#

1
function isValidBST(root) {
2
  const traverse = (root, min, max) => {
3
    if (!root) return true
4
    if (root.val <= min || root.val >= max) return false
5

6
    return (
7
      traverse(root.left, min, root.val) && traverse(root.right, root.val, max)
8
    )
9
  }
10

11
  return traverse(root, -Infinity, Infinity)
12
}

1
function isValidBST(root) {
2
  if (!root) return true
3

4
  const stack = [[root, -Infinity, Infinity]]
5

6
  while (stack.length) {
7
    const [node, min, max] = stack.pop()
8
    if (node.val <= min || node.val >= max) return false
9
    node.left && stack.push([node.left, min, node.val])
10
    node.right && stack.push([node.right, node.val, max])
11
  }
12

13
  return true
14
}