手把手带你刷二叉树（二期）

先来复习一下写树的算法的关键思路：

把题目的要求细化，搞清楚根节点应该做什么，然后剩下的事情抛给前 / 中 / 后序遍历框架即可。 我们千万不要跳到递归的细节里面，你的脑袋能压几个栈。

构造最大二叉树

这是 LeetCode 原题：最大二叉树 (opens new window)

按照我们刚才说的， 先明确根节点做什么？ 对于构造二叉树的问题，根节点要做的就是想办法把自己构造出来。

我们肯定要遍历数组找到最大值 maxValue，把根节点 root 做出来，然后对 maxValue 左边的数组和右边的数组进行递归调用作为 root 的左右子树。

按照题目给出的例子，输入的数组为 [3, 2, 1, 6, 0, 5] ，对于整棵树的根节点来说，其实在做这件事：

function constructMaximumBinaryTree([3, 2, 1, 6, 0, 5]) {
  // 找到数组中最大值
  const root = new TreeNode(6)
  // 递归调用构造左右子树
  root.left = constructMaximumBinaryTree([3, 2, 1])
  root.right = constructMaximumBinaryTree([0, 5])
  return root
}

即 对于每棵子树的根节点来说，只需要找到当前 nums 中的最大值和对应的索引，然后递归调用左右数组构造左右子树即可。

function constructMaximumBinaryTree(nums: number[]): TreeNode {
  if(!nums.length) return null
  
  const max = Math.max(...nums)
	const index = nums.indexOf(max)
  const leftBinaryTree = nums.slice(0, index)
  const rightBinaryTree = nums.slice(index + 1)
  
  const root = new TreeNode(max)
  root.left = constructMaximumBinaryTree(leftBinaryTree)
  root.right = constructMaximumBinaryTree(rightBinaryTree)
  return root
}