GuilinDev

Lc0654

05 August 2008

654 - Maximum Binary Tree

原题概述

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

  1. The root is the maximum number in the array.
  2. The left subtree is the maximum tree constructed from left part subarray divided by the maximum number.
  3. 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:

1
2
3
4
5
6
7
8
9
10

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

      6
    /   \
   3     5
    \    / 
     2  0   
       \
        1

Note:

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

题意和分析

给一个整数数组，创建一个最大二叉树，最大二叉树的定义是最大值为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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        if (nums == null || nums.length == 0) {
            return null;
        }
        return recursion(nums, 0, nums.length - 1);
    }
    private TreeNode recursion(int[] nums, int left, int right) {
        if (left > right) { //终止条件，注意传进来的区间，比如一个元素，left是可以等于right的
            return null;
        }
        int index = findMax(nums, left, right);
        
        // 构建当前节点
        TreeNode node = new TreeNode(nums[index]);
        
        // 递归构建当前结点的左右子树
        node.left = recursion(nums, left, index - 1);
        node.right = recursion(nums, index + 1, right);
        
        return node;
    }
    
    // 返回区间最大值的index
    private int findMax(int[] nums, int left, int right) {
        
        int maxIndex = left;
        
        for (int i = left; i <= right; i++) {
            if (nums[i] > nums[maxIndex]) {
                maxIndex = i;
            }
        }
        
        return maxIndex;
    }
}

迭代，了解一下，用一个数据结构来临时创建节点，然后根据大小特性接入成左子树或右子树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        LinkedList<TreeNode> v = new LinkedList<>();
        for (int num: nums){
            // 先构建当前节点
            TreeNode cur = new TreeNode(num);
            
            // 左边接比较小的部分
            while (!v.isEmpty() && v.peekFirst().val < cur.val){
                cur.left = v.pop();
            }

            // 右边接
            if (!v.isEmpty()){
                v.peekFirst().right = cur;
            }
            v.push(cur);
        }

        return v.peekLast();
    }
}

迭代，了解一下，使用双端队列也可以

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

class Solution {
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        Deque<TreeNode> stack = new LinkedList<>();
        for (int i = 0; i < nums.length; i++) {
            TreeNode current = new TreeNode(nums[i]);
            while (!stack.isEmpty() && stack.peek().val < nums[i]) {
                current.left = stack.pop();
            }
            if (!stack.isEmpty()) {
                stack.peek().right = current;
            }
            stack.push(current);
        }
        return stack.isEmpty() ? null : stack.removeLast();
    }
}
This site is open source. Improve this page.