[游戏开发]构造数组的MaxTree（Java）

分享一个大牛的人工智能教程。零基础！通俗易懂！风趣幽默！希望你也加入到人工智能的队伍中来！请轻击http://www.captainbed.net

package live.every.day.Programming.Stack;

import live.every.day.DataStructure.Tree.BinaryTree.BinaryTreePrinter;
import live.every.day.DataStructure.Tree.BinaryTree.BinaryTreePrinter.Node;

import java.util.HashMap;
import java.util.Stack;

/**
 * 题目：
 * 一个数组的MaxTree定义如下。
 * １、数组必须没有重复元素。
 * ２、MaxTree是一棵二叉树，数组的每一个值对应一个二叉树节点。
 * ３、包括MaxTree树在内且在其中的每一棵子树上，值最大的节点都是树的头。
 * 给定一个没有重复元素的数组arr，写出生成这个数组的MaxTree的函数，要求如果数组长度为N，则时间复杂度为O(N)，额外空间复杂度为O(N)。
 * 
 * 思路：
 * 利用栈。
 *
 * @author Created by LiveEveryDay
 */

public class ConstructMaxTreeOfArray {

    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<>();
        HashMap<Node, Node> lBigMap = new HashMap<>();
        HashMap<Node, Node> rBigMap = new HashMap<>();
        for (int i = 0; i != nArr.length; i++) {
            Node curNode = nArr[i];
            while ((!stack.isEmpty()) && stack.peek().data < curNode.data) {
                popStackSetMap(stack, lBigMap);
            }
            stack.push(curNode);
        }
        while (!stack.isEmpty()) {
            popStackSetMap(stack, lBigMap);
        }
        for (int i = nArr.length - 1; i != -1; i--) {
            Node curNode = nArr[i];
            while ((!stack.isEmpty()) && stack.peek().data < curNode.data) {
                popStackSetMap(stack, rBigMap);
            }
            stack.push(curNode);
        }
        while (!stack.isEmpty()) {
            popStackSetMap(stack, rBigMap);
        }
        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.data < right.data ? left : right;
                if (parent.left == null) {
                    parent.left = curNode;
                } else {
                    parent.right = curNode;
                }
            }
        }
        return head;
    }

    private static void popStackSetMap(Stack<Node> stack, HashMap<Node, Node> map) {
        Node popNode = stack.pop();
        if (stack.isEmpty()) {
            map.put(popNode, null);
        } else {
            map.put(popNode, stack.peek());
        }
    }

    public static void main(String[] args) {
        int[] arr = {3, 4, 5, 1, 2};
        Node h = getMaxTree(arr);
        BinaryTreePrinter.print(h);
    }

}

// ------ Output ------
/*
The binary tree is:
      5
    /   \
  4       2
 /       /
3       1
*/