Keshawn_lu's Blog

Leetcode 654. 最大二叉树

树 单调栈 递归
字数统计: 770阅读时长: 3 min
2022/08/20 Share

题目简介：

给定一个不重复的整数数组 nums 。 最大二叉树 可以用下面的算法从 nums 递归地构建:

  1. 创建一个根节点，其值为 nums 中的最大值。
  2. 递归地在最大值 左边 的 子数组前缀上 构建左子树。
  3. 递归地在最大值 右边 的 子数组后缀上 构建右子树。

返回 nums 构建的 最大二叉树 。

示例 1：

tree1

1
2
3
4
5
6
7
8
9
10
11
12
输入：nums = [3,2,1,6,0,5]
输出：[6,3,5,null,2,0,null,null,1]
解释：递归调用如下所示：
- [3,2,1,6,0,5] 中的最大值是 6 ，左边部分是 [3,2,1] ，右边部分是 [0,5] 。
    - [3,2,1] 中的最大值是 3 ，左边部分是 [] ，右边部分是 [2,1] 。
        - 空数组，无子节点。
        - [2,1] 中的最大值是 2 ，左边部分是 [] ，右边部分是 [1] 。
            - 空数组，无子节点。
            - 只有一个元素，所以子节点是一个值为 1 的节点。
    - [0,5] 中的最大值是 5 ，左边部分是 [0] ，右边部分是 [] 。
        - 只有一个元素，所以子节点是一个值为 0 的节点。
        - 空数组，无子节点。

提示：

  • 1 <= nums.length <= 1000
  • 0 <= nums[i] <= 1000
  • nums 中的所有整数 互不相同

思路：

方法一：

递归，每次将数组中的最大值找出来即可。

时间复杂度：O(n^2)

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {

        if(nums.size() == 0)
            return nullptr;

        int idx = 0;
        for(int i = 1; i < nums.size(); i++){

            if(nums[i] > nums[idx])
                idx = i;
        }

        TreeNode* node = new TreeNode(nums[idx]);
        
        vector<int> left_num(nums.begin(), nums.begin() + idx);
        node -> left = constructMaximumBinaryTree(left_num);

        vector<int> right_num(nums.begin() + idx + 1, nums.end());
        node -> right = constructMaximumBinaryTree(right_num);

        return node;
    }
};

方法二：

利用栈，在遍历元素时，构造每一个元素的最大二叉树。

若遇到的元素比当前栈顶元素小，那么就作为该栈顶元素的右节点并入栈。

若遇到的元素比当前栈顶元素大，则将栈顶元素不断出栈，并且这些元素为当前元素的左节点(因为位置上是在当前元素的左边)。

最后返回栈底元素即可(根节点，最大值)。

时间复杂度：O(n)

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {

        stack<TreeNode*> st;

        for(auto& num : nums){

            TreeNode* node = new TreeNode(num);

            while(!st.empty() && node -> val > st.top() -> val){

                node -> left = st.top();
                st.pop();
            }

            if(!st.empty()){

                st.top() -> right = node;   //作为当前栈顶元素的右节点
            }

            st.push(node);
        }

        TreeNode* res;  //取栈底元素
        while(!st.empty()){

            res = st.top();
            st.pop();
        }
        
        return res;
    }
};
CATALOG
  1. 1. 题目简介：
  2. 2. 思路：
    1. 2.1. 方法一：
    2. 2.2. 方法二：
Total : 424
2023
2022
2021
2020
2019
动态规划 树 深度优先搜索 哈希表 数组 深度优先遍历 单调栈 字符串 双指针 栈 贪心 图 模拟 广度优先搜索 回溯 滑动窗口 二分查找 广度优先遍历 记忆化搜索 数学 链表 前缀和 双向链表 优先队列 拓扑排序 KMP 堆 字典树 递归 并查集 矩阵 位运算 双端队列 吴恩达团队NLP 吴恩达深度学习 线性表
杂谈 算法相关 PAT 2019推理小说阅读计划 NLP 深度学习 大三课程学习 大四课程学习 浙工商OJ 牛客网