【LeetCode】Day149-二叉搜索树转为累加树 & 最短无序连续子数组

题目1、累加树

538. 把二叉搜索树转换为累加树【中等】

题解

反序中序遍历

注意题目中说的二叉树是一棵二叉搜索树，它的最常用的性质就是中序遍历序是单调递增的，所以对它反序中序遍历就可以得到一个单调递减的序列。
在过程中对节点的值进行加和即可得到题目中所求，原树中大于或等于 node.val 的值之和，用这个值去更新原节点值。

class Solution {
    int sum=0;
    public TreeNode convertBST(TreeNode root) {
        if(root!=null){
            convertBST(root.right);
            sum+=root.val;
            root.val=sum;
            convertBST(root.left);
        }
        return root;
    }
}

时间复杂度：$O(n)$

空间复杂度：$O(n)$

题目2、最短无序连续子数组

581. 最短无序连续子数组【中等】

题解

思路
假设把数组分成如下三段，左段和右段是升序数组，中段虽然是无序的，但是满足最小值严格小于左段，最大值严格大于右段。
那么我们的目标就明确了，要找出满足题意的子数组，就要找到中段的起点begin和终点end。

算法

• 从左到右，维护最大值max，和比max小的最大的下标end
• 从右到左，维护最小值min，和比min大的最小的下标begin

从左往右，一开始max是第一个数。如果数组符合要求，那么遍历的每一个数都只会相等或者越来越大，也就是我们只会不停地更新max的值。但是，一旦碰到一个小于max的数，就说明这个数字的位置不对，这个数字一定是在我们最终要重新sort的subarray里的，并且是右边界（因为我们在不断向右探索）。

最终子数组的长度为 终点下标end-起点下标begin+1。

class Solution {
    public int findUnsortedSubarray(int[] nums) {
        int n=nums.length,max=nums[0],min=nums[n-1];
        int begin=0,end=-1;
        for(int i=1;i<n;i++){
            //更新终点
            int num1=nums[i];
            if(num1>=max)
                max=num1;
            else
                end=i;
            //更新起点
            int num2=nums[n-1-i];
            if(num2<=min)
                min=num2;
            else
                begin=n-1-i;
        }
        return end-begin+1;
    }
}

时间复杂度：$O(n)$

空间复杂度：$O(1)$