为什么以下代码会生成运行时错误？

Question

给定一个没有重复的整数数组。在此数组上构建的最大树定义如下：根是数组中的最大数。左子树是由左部分子数组除以最大数构造的最大树。右子树是由右部分子数组除以最大数构造的最大树。通过给定数组构造最大树并输出该树的根节点。Input: [3,2,1,6,0,5]Output: return the tree root node representing the following tree:      6    /   \   3     5    \    /      2  0          \        1/** * Definition for a binary tree node. */function TreeNode(val) {  this.val = val;  this.left = this.right = null;}/** * @param {number[]} nums * @return {TreeNode} */var constructMaximumBinaryTree = function(nums) {  if (nums == null)    return null;  return helper(nums, 0, nums.length - 1);};function helper(nums, low, high) {  if (low > high) {    return null;  }  let maxIndex = 0;  for (let i = low; i <= high; i++) {    if (nums[maxIndex] < nums[i]) {      maxIndex = i;    }  }  let node = new TreeNode(nums[maxIndex]);  node.left = helper(nums, 0, maxIndex - 1);  node.right = helper(nums, maxIndex + 1, high);  return node;};console.log(constructMaximumBinaryTree([3,2,1,6,0,5]));

Answer 1

问题是线路

let maxindex = 0;

您只关心从low到范围的最大元素high。如果nums[0]高于该范围内的任何元素，您将找不到它，也不会正确划分该子序列。这导致无限递归。

将其更改为：

let maxindex = low;

以便它只与范围内的元素进行比较。您可以从 开始for循环low+1。

/**

 * Definition for a binary tree node.

 */

function TreeNode(val) {

  this.val = val;

  this.left = this.right = null;

}

/**

 * @param {number[]} nums

 * @return {TreeNode}

 */

var constructMaximumBinaryTree = function(nums) {

  if (nums == null)

    return null;

  return helper(nums, 0, nums.length - 1);

};

function helper(nums, low, high) {

  if (low > high) {

    return null;

  }

  let maxIndex = low;

  for (let i = low+1; i <= high; i++) {

    if (nums[maxIndex] < nums[i]) {

      maxIndex = i;

    }

  }

  let node = new TreeNode(nums[maxIndex]);

  node.left = helper(nums, 0, maxIndex - 1);

  node.right = helper(nums, maxIndex + 1, high);

  return node;

};

console.log(constructMaximumBinaryTree([3,2,1,6,0,5]));