1月16日代码随想录最大二叉树

654.最大二叉树

给定一个不重复的整数数组?nums?。?最大二叉树?可以用下面的算法从?nums?递归地构建:

1. 创建一个根节点，其值为?nums?中的最大值。
2. 递归地在最大值?左边?的?子数组前缀上?构建左子树。
3. 递归地在最大值?右边?的?子数组后缀上?构建右子树。

返回?nums?构建的?最大二叉树?。

示例 1：

输入：nums = [3,2,1,6,0,5]
输出：[6,3,5,null,2,0,null,null,1]
解释：递归调用如下所示：
- [3,2,1,6,0,5] 中的最大值是 6 ，左边部分是 [3,2,1] ，右边部分是 [0,5] 。
    - [3,2,1] 中的最大值是 3 ，左边部分是 [] ，右边部分是 [2,1] 。
        - 空数组，无子节点。
        - [2,1] 中的最大值是 2 ，左边部分是 [] ，右边部分是 [1] 。
            - 空数组，无子节点。
            - 只有一个元素，所以子节点是一个值为 1 的节点。
    - [0,5] 中的最大值是 5 ，左边部分是 [0] ，右边部分是 [] 。
        - 只有一个元素，所以子节点是一个值为 0 的节点。
        - 空数组，无子节点。

示例 2：

输入：nums = [3,2,1]
输出：[3,null,2,null,1]

提示：

• 1 <= nums.length <= 1000
• 0 <= nums[i] <= 1000
• nums?中的所有整数?互不相同

思路

乍一看题面花里胡哨的，但其实就是在数组里找个最大值当作根节点，然后左边部分就是左子树，右边部分就是右子树，再重复同样的构造过程，用递归法很容易得到结果

class Solution {
    
    public TreeNode constructMaximumBinaryTree(int[] nums) {
    
        return helper(nums,0,nums.length-1);
    }
    public TreeNode helper(int[] nums,int left,int right){
        if(left>right){
            return null;
        }
        int best=left;
        for(int i=left+1;i<=right;i++){
            if(nums[i]>nums[best]){
                best=i;
            }
        }
        TreeNode root=new TreeNode(nums[best]);
        root.left=helper(nums,left,best-1);
        root.right=helper(nums,best+1,right);
        return root;
    }
}

方法二

递归法的时间复杂度是on2，我们可以用单调栈的方法只遍历一次数组就构造出完整的二叉树。单调栈的基本思路是这样的：1、如果栈顶元素大于待插入的元素，那么直接入栈，同时，栈顶.right=待插入元素2、小于，栈顶元素出栈，同时待插入元素.left=栈顶元素。

class Solution {

    public TreeNode constructMaximumBinaryTree(int[] nums) {
        Deque<TreeNode> deque=new ArrayDeque();
        for(int i=0;i<nums.length;i++){
            TreeNode node=new TreeNode(nums[i]);
            while(!deque.isEmpty()){
                TreeNode topNode=deque.peekLast();
                if(topNode.val>node.val){
                    deque.addLast(node);
                    topNode.right=node;
                    break;
                }else {
                    deque.removeLast();
                    node.left=topNode;
                }
            }
            if(deque.isEmpty()){
                deque.addLast(node);
            }
        }
        return deque.peek();
    }

}

总结

第一次接触单调栈，思路不是很清楚，可以看看这篇博客，讲的不错

【算法】单调栈 - 小拙 - 博客园 (cnblogs.com)