654. 最大二叉树
题目描述
输入一个各元素互不相同的整数数组 nums，按下面的规则递归地建一棵二叉树。
取当前数组中的最大值作为根。最大值左侧的那段元素用同样的方法建成左子树，右侧的那段元素建成右子树。某一侧没有元素时，对应的子树为空。
返回建好的树的根节点，输出用层序数组表示，null 表示空位。
示例 1
输入：nums = [3,2,1,6,0,5] 输出：[6,3,5,null,2,0,null,null,1]
解释：6 为根；左侧 [3,2,1] 以 3 为根，并沿右侧依次挂上 2 和 1；右侧 [0,5] 以 5 为根，0 是它的左孩子。
示例 2
输入：nums = [3,2,1] 输出：[3,null,2,null,1]
解释：数组递减，每个节点都只有右孩子。
数据范围
1 <= nums.length <= 10000 <= nums[i] <= 1000nums中的元素互不相同。
解题思路：递归分治
直接按定义递归：build(lo, hi) 负责区间 nums[lo..hi]。区间为空返回 None；否则扫一遍找到最大值下标 m，用 nums[m] 建节点，左子树 = build(lo, m-1)，右子树 = build(m+1, hi)。只传下标不切片，避免复制数组。
为什么正确
build(lo, hi) 返回的树恰好包含 nums[lo..hi] 的全部元素，其中序遍历就是这段区间本身。
复杂度分析
时间平均 O(n log n)，最坏 O(n²)（数组有序时树退化成链）；用单调栈可以做到 O(n)。空间 O(n) 递归栈。
易错点
左右子区间要排除 m 自己：左是 [lo, m-1]，右是 [m+1, hi]；写成 [lo, m] 会无限递归。空区间的判断是 lo > hi，不是 lo >= hi（否则丢掉单元素区间）。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:
def build(lo, hi):
if lo > hi:
return None
m = lo
for i in range(lo + 1, hi + 1):
if nums[i] > nums[m]:
m = i
node = TreeNode(nums[m])
node.left = build(lo, m - 1)
node.right = build(m + 1, hi)
return node
return build(0, len(nums) - 1)class Solution {
TreeNode build(int[] nums, int lo, int hi) {
if (lo > hi)
return null;
int m = lo;
for (int i = lo + 1; i <= hi; i++)
if (nums[i] > nums[m])
m = i;
TreeNode node = new TreeNode(nums[m]);
node.left = build(nums, lo, m - 1);
node.right = build(nums, m + 1, hi);
return node;
}
public TreeNode constructMaximumBinaryTree(int[] nums) {
return build(nums, 0, nums.length - 1);
}
}class Solution {
TreeNode* build(vector<int>& nums, int lo, int hi) {
if (lo > hi)
return nullptr;
int m = lo;
for (int i = lo + 1; i <= hi; i++)
if (nums[i] > nums[m])
m = i;
TreeNode* node = new TreeNode(nums[m]);
node->left = build(nums, lo, m - 1);
node->right = build(nums, m + 1, hi);
return node;
}
public:
TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
return build(nums, 0, (int)nums.size() - 1);
}
};func constructMaximumBinaryTree(nums []int) *TreeNode {
var build func(lo, hi int) *TreeNode
build = func(lo, hi int) *TreeNode {
if lo > hi {
return nil
}
m := lo
for i := lo + 1; i <= hi; i++ {
if nums[i] > nums[m] {
m = i
}
}
node := &TreeNode{Val: nums[m]}
node.Left = build(lo, m-1)
node.Right = build(m+1, hi)
return node
}
return build(0, len(nums)-1)
}var constructMaximumBinaryTree = function(nums) {
const build = (lo, hi) => {
if (lo > hi)
return null;
let m = lo;
for (let i = lo + 1; i <= hi; i++)
if (nums[i] > nums[m])
m = i;
const node = new TreeNode(nums[m]);
node.left = build(lo, m - 1);
node.right = build(m + 1, hi);
return node;
};
return build(0, nums.length - 1);
};function constructMaximumBinaryTree(nums: number[]): TreeNode | null {
const build = (lo: number, hi: number): TreeNode | null => {
if (lo > hi)
return null;
let m = lo;
for (let i = lo + 1; i <= hi; i++)
if (nums[i] > nums[m])
m = i;
const node = new TreeNode(nums[m]);
node.left = build(lo, m - 1);
node.right = build(m + 1, hi);
return node;
};
return build(0, nums.length - 1);
}其他解法
递归分治直接照定义找最大值，数组有序时退化到 O(n²)；单调栈用“左右两侧第一个更大的数”确定父节点，一次扫描建好整棵树。
解法 2：单调栈 时间 O(n)，空间 O(n)
从左到右扫描，维护一个节点值从底到顶递减的栈。对新节点，把栈顶比它小的节点依次弹出，最后弹出的那个就是它的左孩子。弹完后栈非空，就把新节点设为栈顶的右孩子。再把新节点入栈。扫描结束后栈底就是根。
每个节点只入栈出栈一次，线性时间。代价是要想清楚“左侧第一个更大的数”与父子关系的对应，不如递归直观。
class Solution:
def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:
stk = []
for v in nums:
node = TreeNode(v)
last = None
while stk and stk[-1].val < v:
last = stk.pop()
node.left = last
if stk:
stk[-1].right = node
stk.append(node)
return stk[0]class Solution {
public TreeNode constructMaximumBinaryTree(int[] nums) {
Deque<TreeNode> stk = new ArrayDeque<>();
for (int v : nums) {
TreeNode node = new TreeNode(v);
TreeNode last = null;
while (!stk.isEmpty() && stk.peek().val < v) last = stk.pop();
node.left = last;
if (!stk.isEmpty()) stk.peek().right = node;
stk.push(node);
}
return stk.peekLast();
}
}class Solution {
public:
TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
vector<TreeNode*> stk;
for (int v : nums) {
TreeNode* node = new TreeNode(v);
TreeNode* last = nullptr;
while (!stk.empty() && stk.back()->val < v) {
last = stk.back();
stk.pop_back();
}
node->left = last;
if (!stk.empty()) stk.back()->right = node;
stk.push_back(node);
}
return stk[0];
}
};func constructMaximumBinaryTree(nums []int) *TreeNode {
stk := []*TreeNode{}
for _, v := range nums {
node := &TreeNode{Val: v}
var last *TreeNode
for len(stk) > 0 && stk[len(stk)-1].Val < v {
last = stk[len(stk)-1]
stk = stk[:len(stk)-1]
}
node.Left = last
if len(stk) > 0 {
stk[len(stk)-1].Right = node
}
stk = append(stk, node)
}
return stk[0]
}var constructMaximumBinaryTree = function(nums) {
const stk = [];
for (const v of nums) {
const node = new TreeNode(v);
let last = null;
while (stk.length && stk[stk.length - 1].val < v) last = stk.pop();
node.left = last;
if (stk.length) stk[stk.length - 1].right = node;
stk.push(node);
}
return stk[0];
};function constructMaximumBinaryTree(nums: number[]): TreeNode | null {
const stk: TreeNode[] = [];
for (const v of nums) {
const node = new TreeNode(v);
let last: TreeNode | null = null;
while (stk.length && stk[stk.length - 1].val < v) last = stk.pop()!;
node.left = last;
if (stk.length) stk[stk.length - 1].right = node;
stk.push(node);
}
return stk[0];
}