建立数组的MaxTree+栈+HashMap+二叉树的建立

题目：

一个数组的MaxTree定义如下：

数组必须没有重复元素；

MaxTree是一个二叉树，数组的每一个值对应一个二叉树节点；

包括MaxTree树在内且在其中的每一颗子树上，值最大的节点都是数的头。

给定一个没有重复元素的数组arr，写出生成这个数组的MaxTree的函数，要求如果数组长度为N，则时间复杂度为O(N)、额外空间复杂度为O(N) 。

分析： 利用下列原则可以建立题目要求的树：

1每一个数的父节点是它左边第一个比它大的数和它右边第一个比它大的数中，较小的那个。
2如果一个数左边没有比它大的数，右边也没有，也就是说，这个数是整个数组的最大值，那个这个是树根节点。

证明省略。

如何快速地找到每一个数左右两边第一个比它大的树呢？

用栈，找每个数左边第一个比它大的数时，从左到右遍历每个数，栈中保持从上到下递增序列，新来的数不停的利用pop弹出栈顶，直到栈顶比新数大或没有数。 该方法，每个数进栈一次，出栈一次，时间复杂度为O(N)。

代码如下：

import java.util.*;
public class Main {
	public static void main(String[]args){
		Main test = new Main() ; 
		int []arr = {3 , 4 , 5 , 1 , 2} ;
		Node head = test.getMaxTree(arr) ;	 
		test.preOrder(head); //按照前序遍历二叉树
    }
	public Node getMaxTree(int[] arr){
		Node [] nArr = new Node[arr.length] ; //声明
		for(int i = 0 ; i stack = new Stack() ;
		HashMap lBigMap = new HashMap() ;
		for(int i = 0 ; i rBigMap = new HashMap() ;
		for(int i = nArr.length -1 ; i >= 0 ; i--){
			Node cur = nArr[i] ;
			while(!stack.empty() && stack.peek().value  stack, HashMap map) {
		// TODO Auto-generated method stub
		Node popNode = stack.pop() ; //出栈的时候，确定好了映射关系
		if(stack.isEmpty()){
			map.put(popNode , null) ;
		}
		else{
			map.put(popNode , stack.peek()) ;
		}
	}
	
	//前序遍历二叉树
	public void preOrder(Node head){
		if(head != null){
			System.out.println(head.value);
			preOrder(head.left) ;
			preOrder(head.right) ;
		}
	}		
}
class Node{
	int value ;
	Node left ;
	Node right ;
	public Node(int value){
		this.value = value ;
		left = right = null ; //不能省略，创建树时有效
	}
}