描述

分析

注意类似用数组构造二叉树的题目，每次分隔尽量不要定义新的数组，而是通过下标索引直接在原数组上操作，这样可以节约时间和空间上的开销。

实现

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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
import java.util.LinkedList;
import java.util.Queue;

//654最大二叉树

public class MaximumBinaryTree654{
	public static void main(String[] args){
		TreeNode root = new Solution().constructMaximumBinaryTree(new int[]{3,2,1,6,0,5});
		MyUtils.printBinaryTree(root);
	}
}

class Solution {
    public TreeNode constructMaximumBinaryTree(int[] nums) {
    	return findRootNode(nums, 0, nums.length);//前闭后开
    }

    private TreeNode findRootNode(int[] nums, int leftIndex, int rightIndex){
    	//1. 处理叶子节点和 null 节点
    	if (rightIndex - leftIndex < 1) {
    		//null 节点
    		return null;
    	}
    	if(rightIndex - leftIndex == 1){
    		//叶子节点
    		return new TreeNode(nums[leftIndex]);
    	}
    	//2. 找到 nums 中的最大值以及 maxValueIndex
    	int maxValueIndex = leftIndex, maxValue = nums[leftIndex];
    	for (int i = leftIndex + 1; i < rightIndex; i++) {
    		if (nums[i] > maxValue) {
    			maxValue = nums[i];
    			maxValueIndex = i;
    		}
    	}
    	//3. 设置 rootNode 以及 left 和 right, 并返回
    	TreeNode root = new TreeNode(maxValue);
    	root.left = findRootNode(nums, leftIndex, maxValueIndex);
    	root.right = findRootNode(nums, maxValueIndex + 1, rightIndex);
    	return root;
    }
}

class TreeNode {
	int val;
	TreeNode left;
	TreeNode right;

	public TreeNode(){};
	public TreeNode(int val){this.val = val;}
	public TreeNode(int val, TreeNode left, TreeNode right){
		this.val = val;
		this.left = left;
		this.right = right;
	}
}

class MyUtils{
	//层序遍历
	public static void printBinaryTree(TreeNode root){
		Queue<TreeNode> queue = new LinkedList<>(); 
		queue.offer(root);
		int size;
		TreeNode temp;
		while(!queue.isEmpty()){
			size = queue.size();
			for (int i = 0; i < size; i++) {
				temp = queue.poll();
				System.out.print(temp.val + "\t");
				if(temp.left != null) queue.offer(temp.left);
				if(temp.right != null) queue.offer(temp.right);
			}
		}
	}
}

总结