个人主页网站_广州科技公司有哪些_关键词排名seo优化_友情链接工具

leetcode 654

思路

首先找到数组中最大的值，作为根节点，然后左子树就递归最大值的左边数组，右子树就递归最大值右侧的数组，分别也找到最大值作为节点，当数组不存在的时候说明递归结束，没有节点可递归，如果数组中只存在一个值的时候，也没必要再去专门查询一次最大值，因为只有当前一个值，那可以直接构造当前节点

实现

class TreeNode {constructor(val) {this.val = val;this.left = null;this.right = null;}
}
var constructMaximumBinaryTree = function (nums) {if (!nums.length) return null;const deep = (nums) => {if (!nums.length) return null;if (nums.length === 1) {return new TreeNode(nums[0])}// 获取最大值以及索引const [max, index] = findMaxNumber(nums)// 构造根节点const root = new TreeNode(max);// 分割const left = nums.slice(0, index)const right = nums.slice(index + 1)root.left = deep(left)root.right = deep(right)return root}return deep(nums)
};
var findMaxNumber = function (arr) {let max = -Infinity, index = 0for (let i = 0; i < arr.length; i++) {if (arr[i] > max) {max = arr[i]index = i;}}return [max, index];
}

优化

上面的版本虽然容易理解，但是每次都生成了新的数组，这样很消耗空间和时间，所以进行了优化，利用索引来获取需要的范围，只需要对初始的数组进行修改即可，而节约了构造数组的消耗

class TreeNode {constructor(val) {this.val = val;this.left = null;this.right = null;}
}
var constructMaximumBinaryTree = function (nums) {const deep = (nums, left, right) => {if (left > right) return null;let max = -Infinity, index = -1;for (let i = left; i <= right; i++) {if (nums[i] > max) {max = nums[i]index = i;}}let root = new TreeNode(max);root.left = deep(nums, left, index - 1)root.right = deep(nums, index + 1, right)return root;}return deep(nums, 0, nums.length - 1)
};