深度优先遍历 DFS
解题思路
找到数组的最大值和最大值的索引，并设置 root 的值为最大值，并以最大值为界限分成左右两个数组 nums1、nums2；
调用 construct(nums1) 创建根节点的左孩子，递归执行此操作，创建根节点的整个左子树；
类似的，调用 construct(nums2) 创建根节点的右子树；
复杂度
-
时间复杂度：
O(n^2)，其中 n 是数组 nums 的长度；在最坏的情况下，数组严格递增或递减，需要递归 n 层，第 i (0≤i<n) 层需要遍历 n−i 个元素以找出最大值； -
空间复杂度：
O(n)；
代码实现
var constructMaximumBinaryTree = function (nums) {
if (nums.length === 0) return null;
// 寻找最大值
let max = Math.max(...nums);
let index = nums.indexOf(max);
// 构建树
let root = new TreeNode(max);
root.left = constructMaximumBinaryTree(nums.slice(0, index));
root.right = constructMaximumBinaryTree(nums.slice(index + 1));
return root;
};
单调栈
图解
复杂度
-
时间复杂度：
O(n)； -
空间复杂度：
O(n)；
实现代码
var constructMaximumBinaryTree = function (nums) {
const n = nums.length;
const stack = []; // 单调递减栈，存储索引
const tree = new Array(n).fill(0);
for (let i = 0; i < n; ++i) {
// 1. 将每个元素实例化成节点，放入 tree 中
tree[i] = new TreeNode(nums[i]);
// 2. 维护一个单调递减栈，如果当前元素大于栈顶元素，则栈顶元素出栈，直到当前元素可以入栈为止
while (stack.length && nums[i] > nums[stack[stack.length - 1]]) {
// 2-1. 将当前值的左节点更新为栈顶元素
tree[i].left = tree[stack[stack.length - 1]];
// 2-2. 栈顶元素出栈
stack.pop();
}
// 3. 将单调栈中的节点，串联起来
if (stack.length) tree[stack[stack.length - 1]].right = tree[i];
// 4. 当前元素入 单调递减栈
stack.push(i);
}
// 5. 返回栈顶元素，栈顶元素就是根节点
return tree[stack[0]];
};
打赏作者
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 513. 找树左下角的值
上一篇
评论
