LeetCode: 654. Maximum Binary Tree

友情支持

如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜

支付宝

有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。

wx jikerizhi

公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。

654. Maximum Binary Tree

LeetCode - Maximum Binary Tree

Given an integer array with no duplicates. A maximum tree building on this array is defined as follow:

The root is the maximum number in the array.
The left subtree is the maximum tree constructed from left part subarray divided by the maximum number.
The right subtree is the maximum tree constructed from right part subarray divided by the maximum number.

Construct the maximum tree by the given array and output the root node of this tree.

Example 1:

Input: [3,2,1,6,0,5]
Output: return the tree root node representing the following tree:

      6
    /   \
   3     5
    \    /
     2  0
       \
        1

Note:

The size of the given array will be in the range [1,1000].

思路分析

一、递归

 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
/**
 * @author D瓜哥 · https://www.diguage.com
 * @since 2024-06-26 14:34:18
 */
public TreeNode constructMaximumBinaryTree(int[] nums) {
  if (nums == null || nums.length == 0) {
    return null;
  }
  return dfs(nums, 0, nums.length - 1);
}

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

private int maxIndex(int[] nums, int left, int right) {
  if (left == right) {
    return left;
  }
  int result = left;
  Integer max = nums[left];
  for (int i = left + 1; i <= right; i++) {
    if (max < nums[i]) {
      max = nums[i];
      result = i;
    }
  }
  return result;
}

 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
/**
 * 递归实现
 *
 * @author D瓜哥 · https://www.diguage.com
 * @since 2024-07-07 22:41:38
 */
public TreeNode constructMaximumBinaryTree(int[] nums) {
  return constructMaximumBinaryTree(nums, 0, nums.length - 1);
}

private TreeNode constructMaximumBinaryTree(int[] nums, int start, int end) {
  if (start > end) {
    return null;
  }
  int index = start;
  for (int i = start; i <= end; i++) {
    if (nums[i] > nums[index]) {
      index = i;
    }
  }
  TreeNode root = new TreeNode(nums[index]);
  root.left = constructMaximumBinaryTree(nums, start, index - 1);
  root.right = constructMaximumBinaryTree(nums, index + 1, end);
  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
26
27
28
29
30
31
32
/**
 * 参考 https://leetcode.cn/problems/maximum-binary-tree/solutions/1762400/zhua-wa-mou-si-by-muse-77-myd7/[654. 最大二叉树 - 图解LeetCode^]
 *
 * TODO: 为什么执行效率非常低啊？
 *
 * @author D瓜哥 · https://www.diguage.com
 * @since 2024-06-26 14:34:18
 */
public TreeNode constructMaximumBinaryTree(int[] nums) {
  if (nums == null || nums.length == 0) {
    return null;
  }
  Deque<TreeNode> deque = new ArrayDeque<>();
  for (int i = 0; i < nums.length; i++) {
    TreeNode node = new TreeNode(nums[i]);
    while (!deque.isEmpty()) {
      TreeNode topNode = deque.peekLast();
      if (topNode.val > node.val) {
        deque.addLast(node);
        topNode.right = node;
        break;
      } else {
        deque.removeLast();
        node.left = topNode;
      }
    }
    if (deque.isEmpty()) {
      deque.addLast(node);
    }
  }
  return deque.peek();
}

参考资料

654. 最大二叉树 - 图解LeetCode