LeetCode654-最大二叉树

发表于 | 分类于

题目链接

英文链接：https://leetcode.com/problems/maximum-binary-tree/

中文链接：https://leetcode-cn.com/problems/maximum-binary-tree/

题目详述

给定一个不含重复元素的整数数组。一个以此数组构建的最大二叉树定义如下：

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

通过给定的数组构建最大二叉树，并且输出这个树的根节点。

Example 1:

1
2
3
4
5
6
7
8
9
10
输入: [3,2,1,6,0,5]
输入: 返回下面这棵树的根节点：

      6
    /   \
   3     5
    \    / 
     2  0   
       \
        1

注意:

  1. 给定的数组的大小在 [1, 1000] 之间。

题目详解

方法一：按照题目定义进行递归构建，时间复杂度为 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
public class LeetCode_00654 {

    public TreeNode constructMaximumBinaryTree(int[] nums) {
        return dfs(nums, 0, nums.length - 1);
    }

    private TreeNode dfs(int[] nums, int l, int r) {
        if (l > r) {
            return null;
        }
        int index = l;
        for (int i = l + 1; i <= r; ++i) {
            if (nums[i] > nums[index]) {
                index = i;
            }
        }
        TreeNode root = new TreeNode(nums[index]);
        root.left = dfs(nums, l, index - 1);
        root.right = dfs(nums, index + 1, r);
        return root;
    }
}

方法二：运用单调队列。

假设索引 0~i-1 的结点构建的二叉树如下：

1
2
3
4
5
6
7
    A
   / \
...   B
     / \
  ...   C
       / \
    ...   ...

当添加索引为 i 的结点时，若 D.val > A.val，因为 D 在 A 的右边，所以 A 一定在 D 的左子树中。则变为

1
2
3
4
5
6
7
8
9
      D
     /
    A
   / \
...   B
     / \
  ...   C
       / \
    ...   ...

若 D.val < A.val，因为 D 在 A 的右边，所以 D 一定在 A 的右子树中。接下来对 B、C 做同样的判断。若 C.val < D.val，则变为下图。

1
2
3
4
5
6
7
8
9
    A
   / \
...   B
     / \
   ...  D
       /
      C
     / \
  ...   ...
  • 整个思路就是每来一个结点，把它插入到之前构建的树的正确位置。
  • 下面是运用单调队列实现的。单调队列存储的是可能进行插入操作的那条右支链，队首为根结点，队尾为支链的最底层结点。
  • 每个结点最多入队一次，出队一次，时间复杂度为 O(n)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class LeetCode_00654 {

    public TreeNode constructMaximumBinaryTree(int[] nums) {
        if (nums == null || nums.length == 0) {
            return null;
        }
        Deque<TreeNode> deque = new ArrayDeque<>();
        for (int num : nums) {
            TreeNode node = new TreeNode(num);
            while (!deque.isEmpty() && deque.peekLast().val < num) {
                node.left = deque.pollLast();
            }
            if (!deque.isEmpty()) {
                deque.peekLast().right = node;
            }
            deque.offerLast(node);
        }
        return deque.peekFirst();
    }
}