public static Node getMaxTree(int[] arr){ Node[] nArr=new Node[arr.length]; for(int i=0;i!=arr.length;i++){ nArr[i]=new Node(arr[i]); } Stack<Node> stack=new Stack<Node>(); Map<Node,Node> lBigMap=new HashMap<Node,Node>(); Map<Node,Node> rBigMap=new HashMap<Node,Node>(); for(int i=0;i!=nArr.length;i++){ Node curNode=nArr[i]; while(!stack.isEmpty()&&stack.peek().value<curNode.value){ popStackSetMap(stack,lBigMap,rBigMap,curNode); } stack.push(curNode); } while(!stack.isEmpty()){ popStackSetMap(stack,lBigMap,rBigMap,null); } Node head =null; for(int i=0;i!=nArr.length;i++){ Node curNode=nArr[i]; Node left=lBigMap.get(curNode); Node right=rBigMap.get(curNode); if(left==null&&right==null){ head=curNode; }else if(left==null){ if(right.left==null){ right.left=curNode; }else{ right.right=curNode; } }else if(right==null){ if(left.left==null){ left.left=curNode; }else{ left.right=curNode; } }else{ Node parent =left.value<right.value?left:right; if(parent.left==null){ parent.left=curNode; }else{ parent.right=curNode; } } } return head; } public static void popStackSetMap(Stack<Node> stack,Map<Node,Node> lmap,Map<Node,Node> rmap,Node curNode){ Node popNode=stack.pop(); if(stack.isEmpty()){ lmap.put(popNode,null); }else{ lmap.put(popNode, stack.peek()); } rmap.put(popNode, curNode); } 第4题改进版