栈和队列——构造数组的MaxTree（java实现）

亦凉 2022-06-07 00:41 99阅读 0赞

【题目】  
　　定义二叉树节点如下：

class Node{
        public int value;
        public Node left;
        public Node right;
    
        public Node(int data){
            this.value = data;
        }
    }

一个数组的MaxTree定义如下：

· 数组必须没有重复元素

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

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

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

【解答】

以下列原则来建立这棵树：  
　　· 每一个数的父节点是它左边第一个比它大的数和它右边第一个比它大的数中，较小的那个  
　　·如果一个数左边没有比它大的数，右边也没有。也就是说，这个数是整个数组的最大值，那么这个数是MaxTree的头结点

知道了原则，那么如何可能快的找到每一个数左右两边第一个比它大的数呢？利用栈。  
　　找每个数左边第一个比它大的数，从左到右遍历每个数，栈中保持递减序列，新来的数不停地利用Pop出栈顶，直到栈顶比新数大或者没有数。  
　　以\[3,1,2\]为例，首先3入栈，接下来1比3小，直接入栈，并且确定了1左边第一个比它大的数是3；接下来2比1大，1出栈，同时可以确定1右边第一个比它大的数是2；接下来2比3小，2入栈，并且确定了2左边第一个比它大的数是3。此时栈中的元素为\[3,2\]，没有数使它们出栈，所以3和2右边都没有比它大的数。

public 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>();
        HashMap<Node,Node> lBigMap = new HashMap<Node,Node>();
        HashMap<Node,Node> rBigMap = new HashMap<Node,Node>();
        for(int i=0;i!=arr.length;i++){
            Node curNode = nArr[i];
            while((!stack.isEmpty()) && stack.peek().value < curNode.value){
                Node popNode = stack.pop();
                if(stack.isEmpty()){
                    lBigMap.put(popNode,null);
                    rBigMap.put(popNode,curNode);
                }else{
                    lBigMap.put(popNode,stack.peek());
                    rBigMap.put(popNode,curNode);
                }
            }
            stack.push(curNode);
        }
        while(!stack.isEmpty()){
            Node popNode = stack.pop();
            if(stack.isEmpty()){
                lBigMap.put(popNode,null);
                rBigMap.put(popNode,null);
            }else{
                lBigMap.put(popNode,stack.peek());
                rBigMap.put(popNode,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;
    }