前言

当前所有算法都使用测试用例运行过，但是不保证100%的测试用例，如果存在问题务必联系批评指正~

在此感谢左大神的书让我对算法有了新的感悟认识！

问题介绍

原问题
给定一个整数数组，数组没有相同节点，将整数组转为最大值树：
1、树节点和数组中的节点一一对应
2、树为二叉树
3、树节点中满足每一个子树中，父节点都大于子节点即可

解决方案

方案一：
1、栈与队列模块肯定要用栈和队列了，怎么用？
2、直接借鉴大神的想法，数组中每一个数都可以找到左边第一个比自己大的数，右边第一个比自己大的数，如果都没有那就是父节点，如果两边都有比自己大的数，那选择较小的为自己的父节点（因为选择较大的，那个比自己大的较小的父节点没面子~咳咳，其实就是防止和较小的父节点抢了同一个父节点从而不能保证最后的树是二叉树了）。
3、那么现在问题就是遍历arr，找到arr中的每一个数的左右第一个比自己大的数，怎么找？看1，用栈吧
4、每遍历一个数都会和栈顶比较，将栈里面比自己小的额都挖出去，直到栈顶比自己大或者栈为空（这一边没有比自己大的数）时，获取左/右边比自己大的数写入map表中，然后将自己push进去。
方案二：
大同小异，比起方案一，方案二选择了入栈的时候就获取到左/右边比自己大的数，并且在空间利用和循环上做了裁剪和再利用

时间:O(n) 空间O(n)

代码编写

java语言版本

方案一

public class MaxTree {

    /**
     * 辅助栈
     */
    private Stack<MyTreeNode> stackHelper;
    /**
     * 左边第一个比自己小的节点映射
     */
    private Map<MyTreeNode, MyTreeNode> leftMap;
    /**
     * 右边第一个比自己小的节点映射
     */
    private Map<MyTreeNode, MyTreeNode> rightMap;

    public MaxTree() {
        this.stackHelper = new Stack<>();
        this.leftMap = new HashMap<>();
        this.rightMap = new HashMap<>();
    }

    /**
     * 获取最大值树节点
     * @param arrays
     * @return
     */
    public MyTreeNode getMaxTree(Integer[] arrays){
        try{
            List<MyTreeNode> myTreeNodes = new ArrayList<>();
            for (Integer num : arrays){
                myTreeNodes.add(new MyTreeNode(num));
            }
            fillMap(myTreeNodes, "left");
            fillMap(myTreeNodes, "right");
            // 通过map比较得出最后的树结构
            MyTreeNode head = null;
            for (MyTreeNode myTreeNode : myTreeNodes){
                MyTreeNode left = leftMap.get(myTreeNode);
                MyTreeNode right = rightMap.get(myTreeNode);
                if(left == null && right == null){
                    // 都是null，则最大值出现
                    head = myTreeNode;
                    continue;
                }else if(left == null){
                    // 右边是父节点,查看父节点哪边有空位
                    if(right.getLeft() == null){
                        right.setLeft(myTreeNode);
                    }else{
                        right.setRight(myTreeNode);
                    }
                }else if(right == null){
                    if(left.getLeft() == null){
                        left.setLeft(myTreeNode);
                    }else{
                        left.setRight(myTreeNode);
                    }
                }else{
                    // 都不是null,则比较小的那个作为父节点
                    if(left.getData() < right.getData()){
                        if(left.getLeft() == null){
                            left.setLeft(myTreeNode);
                        }else{
                            left.setRight(myTreeNode);
                        }
                    }else{
                        if(right.getLeft() == null){
                            right.setLeft(myTreeNode);
                        }else{
                            right.setRight(myTreeNode);
                        }
                    }

                }
            }
            return head;
        }catch (Exception e){
            e.printStackTrace();
            return null;
        }
    }

    /**
     * 填装map
     */
    private void fillMap(List<MyTreeNode> myTreeNodes, String type) throws Exception{
        Map<MyTreeNode, MyTreeNode> map = new HashMap<>();
        // 首先遍历全部节点，转成node,顺便获取两个map
        if("left".equals(type)){
            map = leftMap;
            for (MyTreeNode node : myTreeNodes){
                // 循环挖比自己小的值，直到比自己大的值出现(其实就是自己左边第一个比自己大的值)，跳出循环
                while (!stackHelper.isEmpty() && node.getData() > stackHelper.peek().getData()){
                    // 挖出栈顶并且当前栈顶的左边第一个最大值就是下一个栈顶
                    poPAndPutMap(stackHelper, map);
                }
                //直到比自己大的值出现了
                stackHelper.push(node);
            }
        }else{
            map = rightMap;
            for (int i = myTreeNodes.size()-1; i >= 0; i--){
                MyTreeNode node = myTreeNodes.get(i);
                while (!stackHelper.isEmpty() && node.getData() > stackHelper.peek().getData()){
                    // 挖出栈顶并且当前栈顶的左边第一个最大值就是下一个栈顶
                    poPAndPutMap(stackHelper, map);
                }
                //直到比自己大的值出现了
                stackHelper.push(node);
            }
        }
        // 到这里栈里面维护了从顶到底 从小到大的顺序，或者为空，这时遍历栈
        while (!stackHelper.isEmpty()){
            poPAndPutMap(stackHelper, map);
        }
    }

    /**
     * 弹出顶并将下个顶放入map中
     * @param stackHelper
     * @param map
     */
    private void poPAndPutMap(Stack<MyTreeNode> stackHelper, Map<MyTreeNode, MyTreeNode> map) throws Exception{
        MyTreeNode node = stackHelper.pop();
        if(stackHelper.isEmpty()){
            map.put(node, null);
        }else{
            map.put(node, stackHelper.peek());
        }

    }

    /**
     * 测试用例
     * @param args
     */
    public static void main(String[] args) {
        // 详解版
        MaxTree maxTree = new MaxTree();
        MyTreeNode maxTree1 = maxTree.getMaxTree(new Integer[]{3, 4, 5, 1, 2});
        printNode(maxTree1);

         简化版
        //MyTreeNode mytreeNode = getMytreeNode(new int[]{3, 4, 5, 1, 2});
         遍历二叉树
        //printNode(mytreeNode);
    }

    private static void printNode(MyTreeNode mytreeNode) {
        if (mytreeNode == null){
            return;
        }
        System.out.println(mytreeNode.getData());
        printNode(mytreeNode.getLeft());
        printNode(mytreeNode.getRight());
    }
}

方案二：简化版本

    public static MyTreeNode getMytreeNode(int[] arr){
        MyTreeNode[] myTreeNodes = new MyTreeNode[arr.length];
        MyTreeNode head = null;
        Stack<MyTreeNode> stack = new Stack<>();
        Map<MyTreeNode, MyTreeNode> treeNodeMap = new HashMap<>();
        for (int i = 0; i < arr.length; i++){
            myTreeNodes[i] = new MyTreeNode(arr[i]);
            treeNodeMap.put(myTreeNodes[i], new MyTreeNode(-1));
            while (!stack.isEmpty() && arr[i] > stack.peek().getData()){
                stack.pop();
            }
            if (stack.isEmpty()){
                treeNodeMap.get(myTreeNodes[i]).setLeft(null);
            }else {
                treeNodeMap.get(myTreeNodes[i]).setLeft(stack.peek());
            }
            stack.push(myTreeNodes[i]);
        }
        stack.clear();
        for (int i = arr.length-1; i >= 0; i--){
            MyTreeNode cur = myTreeNodes[i];
            while (!stack.isEmpty() && cur.getData() > stack.peek().getData()){
                stack.pop();
            }
            if (stack.isEmpty()){
                treeNodeMap.get(cur).setRight(null);
            }else{
                treeNodeMap.get(cur).setRight(stack.peek());
            }
            stack.push(cur);
        }

        for (MyTreeNode myTreeNode : treeNodeMap.keySet()){
            MyTreeNode leftAndRight = treeNodeMap.get(myTreeNode);
            MyTreeNode left = leftAndRight.getLeft();
            MyTreeNode right = leftAndRight.getRight();
            if (left == null && right == null){
                head = myTreeNode;
            }else if (left == null || right == null){
                MyTreeNode parent = left == null? right : left;
                if (parent.getLeft() == null){
                    parent.setLeft(myTreeNode);
                }else {
                    parent.setRight(myTreeNode);
                }
            }else {
                MyTreeNode parent = left.getData() > right.getData() ? right : left;
                if (parent.getLeft() == null){
                    parent.setLeft(myTreeNode);
                }else {
                    parent.setRight(myTreeNode);
                }
            }
        }
        return head;
    }

c语言版本

正在学习中

c++语言版本

正在学习中

思考感悟

1、怎么想到这种方法的
这道题干想，我是想不太到比较好的解法，并且这种想法还需要反证法证明一下，比如为什么这么做就可以获取到二叉树，获取不到三叉树？有兴趣可以自己画一下一边两个孩子时会不会出现
其实这个原理我想了一下，可以倒过来想，如果一个数想成为父节点，那么对于左子和右子来说，这个数一定是他们的最近比他们大的节点中较小的那个，所以只能是这种形式,因此一边的子节点只能有一个,两边最多两个

2、为什么这么实现？
这里栈的想法不是重要的，反而重要的就是：找父节点的过程。遍历的过程就是找父节点的过程，先找候选父节点，然后统一判断确定父节点算法就结束了。
3、以后遇到什么类型的题目要这么想？
以后如果要形成最大值树的过程，除了堆排序之类的，这种方式可以在O（n）的情况下快速形成一个最大值树，但是问题就在于该数又不是平衡二叉树也不是二叉排序树，所以用得地方暂时不知道有哪些，获取最大值倒是可以

写在最后

方案和代码仅提供学习和思考使用，切勿随意滥用！如有错误和不合理的地方，务必批评指正~
如果需要git源码可咨询2260755767@qq.com或在评论区回复即可.
再次感谢左大神的书对我算法的指点迷津！