小鲸鱼的梦境
0%

『LeetCode』654 最大二叉树

发表于 更新于 分类于 Valine：
本文字数： 4.3k 阅读时长 ≈ 4 分钟

题目

654. 最大二叉树

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

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

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

示例 1：

tree1

输入：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 的节点。
- 空数组，无子节点。

示例 2：

img

输入：nums = [3,2,1]
输出：[3,null,2,null,1]

提示：

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

标签

栈, 树, 数组, 分治, 二叉树, 单调栈

相似题目

题解

【最大二叉树】『递归』和『非递归』O(n)解法

递归解法

递归的方法只需按照题意模拟即可

  1. 二叉树的根是数组 nums 中的最大元素。
  2. 左子树是通过数组中 最大值左边部分 递归构造出的最大二叉树。
  3. 右子树是通过数组中 最大值右边部分 递归构造出的最大二叉树。

递归函数签名可以设置为 TreeNode dfs(int[] nums, int left, int right) 分别表示数组引用以及根据数组中 \([left, right]\) 的构建的最大二叉树。

最终结果就是 dfs(nums, 0, nums.length)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# Code language: Python
class Solution:
    def constructMaximumBinaryTree(self, nums: List[int]) -> TreeNode:
        def dfs(left, right):
            if left > right:
                return None
            elif left == right:
                return TreeNode(val=nums[left])
            else:
                idx = right
                for i in range(left, right):
                    if nums[idx] < nums[i]:
                        idx = i
                return TreeNode(nums[idx], dfs(left, idx - 1), dfs(idx + 1, right))
        
        return dfs(0, len(nums) - 1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/* Code language: Java */
class Solution {
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        return dfs(nums, 0, nums.length - 1);
    }

    private TreeNode dfs(int[] nums, int left, int right) {
        if (left > right) return null;
        int idx = right;
        for (int i = left; i < right; ++i) {
            if (nums[idx] < nums[i]) idx = i;
        }
        return new TreeNode(nums[idx], dfs(nums, left, idx - 1), dfs(nums, idx + 1, right));
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/* Code language: C++ */
class Solution {
public:
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        function<TreeNode*(int, int)> dfs = [&](int left, int right) {
            if (left == right) return new TreeNode(nums[left]);
            else {
                int idx = right;
                for (int i = left; i < right; ++i) {
                    if (nums[idx] < nums[i]) idx = i;
                }
                return new TreeNode(nums[idx], idx == left ? nullptr : dfs(left, idx - 1), idx == right ? nullptr : dfs(idx + 1, right));
            }
        };
        return dfs(0, nums.size() - 1);
    }
};
  • 时间复杂度：\(O(n^2)\)，最坏情况是数组单调有序，那么每次查找都需要\(O(n)\)，递归深度\(O(n)\)
  • 空间复杂度：\(O(n)\)，数组单调有序递归深度会达到\(O(n)\)

非递归

可以看到递归算法的最大的不足在于一次一次的扫描数组查找区间内的最大值所在的下标，不难想到这里是可以优化的，容易想到的思路是

  • 线段树，\(O(n)\)建树，\(O(log \, n)\)查询，最后复杂度可以优化到\(O(nlog \, n)\)
  • ST算法，\(O(nlog \, n)\)建表，\(O(1)\)查询，最后复杂度可以优化到\(O(nlog \, n)\)

虽然都可以优化到\(O(nlog \, n)\)，但实现都比较复杂，有兴趣的读者可以自行研究实现

那么有没有可能考虑到只遍历一次数组就能实现的呢，答案是有的

我们考虑两种情况

  1. 数组单调递增，如 [1, 2, 3]

屏幕截图(4).png

  1. 数组单调递减，如 [3, 2, 1]

image

可以看出，数组单调递增时，我们每次创建的新结点的左孩子都是上一步创建的左孩子，例如根据3创建的结点左孩子是根据 [1,2] 创建的最大二叉树；

相反，数组递减时，每次都是在右子树创建新的结点。

但除了单调的情况以外，我们还要考察另外两种峰值的情况：先减后增和先增后减

先增后减 [1, 3, 2]

屏幕截图(6).png

与前面观察一致，看看先减后增 [3, 1, 2]

屏幕截图(7).png

这里似乎不对劲，1比2先出现，但1是2的孩子，并且3的孩子是2，这种情况似乎不能在一次遍历中解决，但其实可以借助栈解决，什么意思呢？

如果想要一轮遍历，那么最大值的左子树好办，因为左边都遍历过了，但右子树还没遍历过，所以我们可以将树先保存到栈中，具体来说，如上面的 [3, 1, 2]，先将3入栈，1比栈顶的3小，所以1也直接入栈，然后2比栈顶的1大，说明2是1的父节点，把1取出来挂在2的左孩子位置，再入栈；可是如果后面还有一个4呢？那么4比2,3都大，所以4是3的父节点，同时在出栈的时候要把2挂在3的右子树上。

（上面是我自己的想到该解法的全部过程思路，看了评论区以后发现这其实是个单调栈🤣）

具体单调栈解决离线RMQ问题的思路可以看这里

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# Code language: Python
class Solution:
    def constructMaximumBinaryTree(self, nums: List[int]) -> TreeNode:
        st = list()
        for num in nums:
            cur = None
            while st and num > st[-1].val:
                pre = st.pop()
                pre.right = cur
                cur = pre
            st.append(TreeNode(num, cur))
        root = None
        while st:
            cur = st.pop()
            cur.right = root
            root = cur
        return root
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/* Code language: Java */
class Solution {
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        Deque<TreeNode> st = new ArrayDeque();
        for (int num: nums) {
            TreeNode cur = null;
            while (!st.isEmpty() && num > st.peekLast().val) {
                TreeNode pre = st.pollLast();
                pre.right = cur;
                cur = pre;
            }
            st.addLast(new TreeNode(num, cur, null));
        }
        TreeNode root = null;
        while (!st.isEmpty()) {
            TreeNode cur = st.pollLast();
            cur.right = root;
            root = cur;
        }
        return root;
    }
}
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
/* Code language: C++ */
class Solution {
public:
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        stack<TreeNode*> st;
        for (int num: nums) {
            TreeNode* cur = nullptr;
            while (!st.empty() && num > st.top()->val) {
                auto pre = st.top();
                pre->right = cur;
                cur = pre;
                st.pop();
            }
            st.push(new TreeNode(num, cur, nullptr));
        }
        TreeNode* root = nullptr;
        while (!st.empty()) {
            auto cur = st.top();
            cur->right = root;
            root = cur;
            st.pop();
        }
        return root;
    }
};
  • 时间复杂度：\(O(n)\)，无论什么情况，每个结点都是入栈出栈一次
  • 空间复杂度：\(O(n)\)，单调递减的情况下栈大小会有\(O(n)\)

如果对你有帮助的话，请给我点个赞吧~

欢迎前往 我的博客 或 Algorithm - Github 查看更多题解

--- ♥ end ♥ ---

欢迎关注我呀~