题目描述

blablabla

样例

blablabla

算法1

(TreeMap) $O(nlogn)$

TreeMap保存node val的顺序，1.把lowerEntry放到当前node.left同时删掉所有lowerEntry（忽略之前所有小的值），2.插入higherEntry的右子树中

Java 代码

public TreeNode constructMaximumBinaryTree(int[] nums) {
        NavigableMap<Integer, TreeNode> map = new TreeMap<>();
        for (int i = 0; i < nums.length; i++) {
            TreeNode node = new TreeNode(nums[i]);
            map.put(nums[i], node);
            TreeNode prevNode = Optional.ofNullable(map.lowerEntry(nums[i])).map(Map.Entry::getValue).orElse(null);
            TreeNode nextNode = Optional.ofNullable(map.higherEntry(nums[i])).map(Map.Entry::getValue).orElse(null);
            if (prevNode != null) {
                node.left = prevNode;
                while (map.lowerEntry(nums[i]) != null) {
                    map.remove(map.lowerKey(nums[i]));
                }
            }
            if (nextNode != null) {
                if (nextNode.right != null) {
                    node.left = nextNode.right;
                }
                nextNode.right = node;
            } 
        }
        return map.lastEntry().getValue();
    }

算法2

(Stack) $O(n)$

TreeMap的算法实际上可以简化成递减stack。一样的思路。

时间复杂度

参考文献

Java 代码

public TreeNode constructMaximumBinaryTree(int[] nums) {
        Stack<TreeNode> decreaseStack = new Stack<>();
        for (int num: nums) {
            TreeNode node = new TreeNode(num);
            TreeNode lowerNode = null;
            while (!decreaseStack.isEmpty() && decreaseStack.peek().val < num) {
                lowerNode = decreaseStack.pop();
            }
            if (lowerNode != null) {
                node.left = lowerNode;
            }
            if (!decreaseStack.isEmpty()) {
                TreeNode higherNode = decreaseStack.peek();
                if (higherNode.right != null) {
                    node.left = higherNode.right;
                }
                higherNode.right = node;
            }
            decreaseStack.push(node);
        }
        return decreaseStack.firstElement();
    }