LeetCode 654. 最大二叉树

Categories:

题目描述
思路分析
1. 解法一：单调栈（推荐）
相似题目

题目描述

✅ 654. 最大二叉树

思路分析

解法一：单调栈（推荐）

核心思路：

使用单调递减栈维护构建过程。

当前节点作为右孩子连接栈顶小于它的节点。

维护栈中相邻节点的左右关系，最终栈底为根。

复杂度分析：

时间复杂度：O(n)，其中 n 表示数组长度。

空间复杂度：O(n)，用于栈。

import java.util.ArrayDeque;
import java.util.Deque;

class Solution {
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        Deque<TreeNode> stack = new ArrayDeque<>();

        for (int num : nums) {
            TreeNode cur = new TreeNode(num);
            while (!stack.isEmpty() && stack.peek().val < num) {
                cur.left = stack.pop();
            }
            if (!stack.isEmpty()) {
                stack.peek().right = cur;
            }
            stack.push(cur);
        }

        TreeNode root = null;
        while (!stack.isEmpty()) {
            root = stack.pop();
        }
        return root;
    }
}

func constructMaximumBinaryTree(nums []int) *TreeNode {
	stack := make([]*TreeNode, 0)

	for _, num := range nums {
		cur := &TreeNode{Val: num}
		for len(stack) > 0 && stack[len(stack)-1].Val < num {
			cur.Left = stack[len(stack)-1]
			stack = stack[:len(stack)-1]
		}
		if len(stack) > 0 {
			stack[len(stack)-1].Right = cur
		}
		stack = append(stack, cur)
	}

	var root *TreeNode
	for len(stack) > 0 {
		root = stack[len(stack)-1]
		stack = stack[:len(stack)-1]
	}

	return root
}

相似题目

题目	难度	考察点
105. 从前序与中序遍历序列构造二叉树	中等	递归
106. 从中序与后序遍历序列构造二叉树	中等	递归
889. 根据前序和后序遍历构造二叉树	中等	递归
114. 二叉树展开为链表	中等	树
654. 最大二叉树	中等	栈

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2022/64967511