class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int need = target - nums[i];
            if (map.containsKey(need)) return new int[]{map.get(need), i};
            map.put(nums[i], i);
        }
        return new int[0];
    }
}

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> map = new HashMap<>();
        for (String s : strs) {
            char[] arr = s.toCharArray();
            Arrays.sort(arr);
            String key = new String(arr);
            map.computeIfAbsent(key, k -> new ArrayList<>()).add(s);
        }
        return new ArrayList<>(map.values());
    }
}

class Solution {
    int ans=0;
    public int longestConsecutive(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int x : nums) set.add(x);
        for (int x : set) {
            if (set.contains(x - 1)) continue;
            int len=1;
            while(set.contains(++x)) len++;
            ans = Math.max(ans, len);
        }
        return ans;
    }
}

class Solution {
    public void moveZeroes(int[] nums) {
        int pos=0;
        for(int x:nums){
            if(x!=0) nums[pos++]=x;
        }
        //注意这个api是左闭右开
        Arrays.fill(nums,pos,nums.length,0);
    }
}

class Solution {
    public int maxArea(int[] height) {
        int l = 0, r = height.length - 1, ans = 0;
        while (l < r) {
            ans = Math.max(ans, (r - l) * Math.min(height[l], height[r]));
            if (height[l] < height[r]) l++;
            else r--;
        }
        return ans;
    }
}

class Solution {
    List<List<Integer>> ans=new ArrayList<>();
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        for(int i=0;i<nums.length-2;i++){
            //去重
            if(i>=1&&nums[i]==nums[i-1]) continue;
            int l=i+1, r=nums.length-1;
            while(l<r){
                int sum=nums[i]+nums[l]+nums[r];
                if(sum>0) r--;
                else if(sum<0) l++;
                else {
                    ans.add(Arrays.asList(nums[i],nums[l],nums[r]));
                    while(l<r&&nums[l]==nums[l+1]) l++;
                    while(l<r&&nums[r-1]==nums[r]) r--;
                    l++;
                    // 1 2 2 2 3 4 5 跳到3
                        r--;
                        //到相等的最后一个, 然后跳到不同的下一个
                }
            }
        }
        return ans;
    }
}

class Solution {
    public int trap(int[] height) {
        int l = 0, r = height.length - 1;
        int lMax = 0, rMax = 0, ans = 0;
        while (l < r) {
            lMax = Math.max(lMax, height[l]);
            rMax = Math.max(rMax, height[r]);
            if (lMax < rMax) ans += lMax - height[l++];
            else ans += rMax - height[r--];
        }
        return ans;
    }
}
3 2 5
lmax=3,rmax=5, ans+=lmax-nums[l++]=3-3;
lmax=3,rmax=5, ans+=lmax-nums[l++]=3-2;

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int[] cnt = new int[128];
        int l = 0, ans = 0;
        for (int r = 0; r < s.length(); r++) {
            cnt[s.charAt(r)]++;
            while (cnt[s.charAt(r)] > 1) cnt[s.charAt(l++)]--;
            ans = Math.max(ans, r - l + 1);
            /*注意别写成
                while(++cnt[s.charAt(r)]>1){
                    cnt[s.charAt(l++)]--;
                }
                因为while每次都会判断, 每次都给++cnt(r)
            */
        }
        return ans;
    }
}

class Solution {
    List<Integer> ans = new ArrayList<>();
    public List<Integer> findAnagrams(String s, String p) {
        if (s.length() < p.length()) return ans;
        int[] need = new int[26], win = new int[26];
        //先搞出标准数组
        for (char c : p.toCharArray()) need[c - 'a']++;
        int plen = p.length();
        for (int i = 0; i < s.length(); i++) {
            win[s.charAt(i) - 'a']++;
            //超出了, 先踢出左侧, 在i>=plen时伊始
            if (i >= plen) win[s.charAt(i - m) - 'a']--;
            if (i >= plen - 1 && Arrays.equals(need, win)) ans.add(i - m + 1);
        }
        return ans;
    }
}

class Solution {
        int ans=0;
    public int subarraySum(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, 1);
        //空前缀出现一次
        //别用前缀和数组, 下标麻烦
        /* presum[i] 表示 nums 前 i 个元素之和
        int[] presum = new int[n + 1];
            for (int i = 1; i <= n; i++) {
            presum[i] = presum[i - 1] + nums[i - 1];
        }*/
        int sum = 0;
        for (int x : nums) {
            sum += x;
            ans += map.getOrDefault(sum - k, 0);
            map.put(sum, map.getOrDefault(sum, 0) + 1);
        }
        return ans;
    }
}

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int pos=0;
        int[] ans=new int[nums.length-k+1];
        Deque<Integer> deq=new ArrayDeque<>();
        for(int i=0;i<nums.length;i++){
            //弹出窗口外的
            while(!deq.isEmpty()&&deq.peekFirst()<=i-k) deq.pollFirst();
            //将队列按从大到小排
            while(!deq.isEmpty()&&nums[i]>=nums[deq.peekLast()]) deq.pollLast();
            //加入当前
            deq.addLast(i);
            if(i>=k-1){
                ans[pos++]=nums[deq.peekFirst()];
                //注意ans装的是数, 非位
            }
        }
        return ans;
    }
}

class Solution {
    public String minWindow(String s, String t) {
        if(s.length()<t.length()) return "";
        //统计目标串的词频, 用负数表示
        int[] cnt=new int[256];
        for(char c:t.toCharArray()) cnt[c]--;
        int l=0,start=0,debt=t.length(),minlen=Integer.MAX_VALUE;
        for(int r=0;r<s.length();r++){
        //如果++后<=0, 说明是目标, 则--debt
            if(++cnt[s.charAt(r)]<=0) debt--;
            
            while(debt==0){
                if(r-l+1<=minlen){
                    start=l;
                    minlen=r-l+1;
                }
        //如果--后<0, 说明是目标, 因为不是目标串应该--后>=0
                if(--cnt[s.charAt(l++)]<0) debt++;
            }
            
        }
        return minlen==Integer.MAX_VALUE?"":s.substring(start,start+minlen);
    }
}

class Solution {
    public int maxSubArray(int[] nums) {
        int cur = nums[0], ans = nums[0];
        //防止出现[ -1 ]的情况, 所以不直接设0
        for (int i = 1; i < nums.length; i++) {
            cur = Math.max(nums[i], cur + nums[i]);
            ans = Math.max(ans, cur);
        }
        return ans;
    }
}

class Solution {
    List<int[]> ans=new ArrayList<>();
    public int[][] merge(int[][] intervals) {
        //按第一个数从小到大排
        Arrays.sort(intervals,(a,b)->a[0]-b[0]);
        for(int[] cur:intervals){
            //当前答案是空or两个数组尾首不相接
        if(ans.isEmpty()||ans.get(ans.size()-1)[1]<cur[0]){
                ans.add(cur);
            }else ans.get(ans.size()-1)[1]=Math.max(ans.get(ans.size()-1)[1],cur[1]);
        }
        return ans.toArray(new int[0][]);
        //注意这个写法!
    }
}

class Solution {
    //非常厉害的思维
    public void rotate(int[] nums, int k) {
        //k可能大于长度nums.length;
        k%=nums.length;
        reverse(nums,0,nums.length-1);
        reverse(nums,0,k-1);
        reverse(nums,k,nums.length-1);
    }
    public void reverse(int[] nums,int l,int r){
        while(l<r){
            int tmp=nums[l];
            nums[l++]=nums[r];
            nums[r--]=tmp;
        }
    }
}

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int len=nums.length;
        int[] pre=new int[len]; pre[0]=1;
        for(int i=1;i<len;i++){
            pre[i]=pre[i-1]*nums[i-1];
        }
        //自己写一下前缀和数组和后缀和数组, 即知道累积规则
        int suffix=1;
        for(int i=len-1;i>=0;i--){
            pre[i]*=suffix;
            suffix*=nums[i];
        }
        return pre;
    }
}

class Solution {
    public int firstMissingPositive(int[] nums) {
        int len=nums.length;
        for(int i=0;i<len;i++){
            //发现属于[1~n]的数并且(pos,val)!=(i-1,nums[i])
            while(1<=nums[i]&&nums[i]<=len&&nums[nums[i]-1]!=nums[i]){
                int tmp=nums[nums[i]-1];
                nums[nums[i]-1]=nums[i];
                nums[i]=tmp;
            }
        }
        //再遍历一遍(pos,val)!=(i-1,nums[i])
        for(int i=0;i<len;i++){
            if(nums[i]!=i+1){
                return i+1;
            }
        }
        return len+1;
        //所有学生都在对的位置, [1,2]->3
    }
}

class Solution {
    public void setZeroes(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        boolean row0 = false, col0 = false;
        for (int j = 0; j < n; j++) if (matrix[0][j] == 0) row0 = true;
        for (int i = 0; i < m; i++) if (matrix[i][0] == 0) col0 = true;
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (matrix[i][j] == 0) {
                    matrix[i][0] = 0;
                    matrix[0][j] = 0;
                }
            }
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (matrix[i][0] == 0 || matrix[0][j] == 0) matrix[i][j] = 0;
            }
        }
        if (row0) Arrays.fill(matrix[0], 0);
        if (col0) for (int i = 0; i < m; i++) matrix[i][0] = 0;
    }
}

class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> ans = new ArrayList<>();
        int l=0,r=matrix[0].length-1;
        int top=0,bot=matrix.length-1;
        while(l<=r&&top<=bot){
            for(int i=l;i<=r;i++){
                ans.add(matrix[top][i]);
            }
            top++;
            
            for(int i=top;i<=bot;i++){
                ans.add(matrix[i][r]);
            }
            r--;
            
            //检查边界, 如果这个不符合, 下一个也肯定符合
            //否则下一轮while循环结束, 也即到达最中心一点
            if(top<=bot){
                for(int i=r;i>=l;i--){
                    ans.add(matrix[bot][i]);
                }
                bot--;
            }
            if(l<=r){
                for(int i=bot;i>=top;i--){
                    ans.add(matrix[i][l]);
                }
                l++;
            }
        }
        return ans;
    }
}

class Solution {
    public void rotate(int[][] matrix) {
        //本题本质就是对角线交换+左右反转
        int rows=matrix.length, cols=matrix[0].length;
        for(int i=0;i<rows;i++){
            //注意这里只需要到对角线就行了
            for(int j=0;j<i;j++){
                if(i==j) continue;
                int tmp = matrix[i][j];
                matrix[i][j]=matrix[j][i];
                matrix[j][i]=tmp;
            }
        }
        for(int[] row:matrix){
            int l=0,r=cols-1;
            while(l<r){
                int tmp=row[l];
                row[l++]=row[r];
                row[r--]=tmp;
            }
        }
    }
}

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int i = 0, j = matrix[0].length - 1;
        while (i < matrix.length && j >= 0) {
            if (matrix[i][j] == target) return true;
            if (matrix[i][j] > target) j--;
            else i++;
        }
        return false;
    }
}

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode a = headA, b = headB;
        while (a != b) {
	        //注意这里是等于null才变向
            a = (a == null) ? headB : a.next;
            b = (b == null) ? headA : b.next;
        }
        return a;
        //or b
    }
}

a:x
b:y
公共:z
a: x z y z
b: y z x z

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode pre=null,cur=head;
        while(cur!=null){
            //先保住下一个, 再转向
            ListNode nxt=cur.next;
            cur.next=pre;
            pre=cur;
            cur=nxt;
        }
        return pre;
    }
}

class Solution {
    public boolean isPalindrome(ListNode head) {
        ListNode slow=head,fast=head;
        while(fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
        }
        //反转前半段到slow正好
        ListNode pre=null;
        while(head!=slow){
            ListNode nxt=head.next;
            head.next=pre;
            pre=head;
            head=nxt;
        }
        slow= fast==null?slow:slow.next;
        while(slow!=null){
            if(slow.val!=pre.val) return false;
            //注意别忘记走
            slow=slow.next;
            pre=pre.next;
        }
        return true;
    }
}

public class Solution {
    public boolean hasCycle(ListNode head) {
            //如果有环必定相遇的!!!!!!!!!!!!!!!!!!!1
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) return true;
        }
        return false;
    }
}

public class Solution {
    public ListNode detectCycle(ListNode head) {
        //slow=b=(kc-a), fast=2b
        //fast-slow=kc--> b=kc-a-->差a到kc完整的圆!
        //head到入环口也是a, 所以while(slow!=head)
        ListNode fast=head, slow=head;
        while(fast!=null && fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
            //有环必相遇
            if(fast==slow){
	            //相遇则此时head和slow齐步走, 必定到环口
                while(slow!=head){
                    slow=slow.next;
                    head=head.next;
                }
                return slow;
            }
        }
        return null;
    }
}

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode dummy=new ListNode(0),cur=dummy;
        ListNode p1=list1,p2=list2;
        while(p1!=null && p2!=null){
            if(p1.val<=p2.val){
                cur.next=p1;
                p1=p1.next;
            }else {
                cur.next=p2;
                p2=p2.next;
            }
            cur=cur.next;
        }
        cur.next= p1==null?p2:p1;
        return dummy.next;
    }
    }

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummy=new ListNode(0), cur=dummy;
        int carry=0,sum=0;
        while(l1!=null||l2!=null||carry!=0){
            //这里主要要加上上一位的进位!!!!!!!!!
            sum=getVal(l1)+getVal(l2)+carry;
            carry=sum/10;
            cur.next=new ListNode(sum%10);
            cur=cur.next;
            l1=l1==null?null:l1.next;
            l2=l2==null?null:l2.next;
        }
        return dummy.next;
    }
    public int getVal(ListNode p){
        return p==null?0:p.val;
    }
}

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0, head);
        ListNode fast = dummy, slow = dummy;
        for (int i = 0; i < n; i++) fast = fast.next;
        //注意这里是刚好走到最后一个节点, fast!=null则是走到最后一个节点的下一个
        while (fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }
        slow.next = slow.next.next;
        return dummy.next;
    }
}

class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode dummy=new ListNode(0,head);
        ListNode node0=dummy, node1=head;
        while(node1!=null&&node1.next!=null){
            ListNode node2=node1.next;
            ListNode node3=node2.next;
            //改签
            node0.next=node2;
            node2.next=node1;
            node1.next=node3;
            
            //更新好下一轮
            node0=node1;
            node1=node3;
        }
        return dummy.next;
    }
}

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        //计算总长度, 好控制循环次数
        int len=0;
        ListNode cur=head;
        while(cur!=null){ cur=cur.next; len++;}
        ListNode dummy=new ListNode(0,head);
        ListNode p0=dummy, pre=null;
        cur=head;
        
        while(len>=k){
            for(int i=0;i<k;i++){
                ListNode nxt=cur.next;
                cur.next=pre;
                pre=cur;
                cur=nxt;
            }
            //标记链表的尾巴
            ListNode nxt=p0.next;
            //连接链表的首
            p0.next=pre;
            //尾连下一条首
            nxt.next=cur;
            //继续下一轮
            p0=nxt;
            len-=k;
        }
        return dummy.next;
    }
}

class Solution {
    public Node copyRandomList(Node head) {
        Map<Node,Node> map = new HashMap<>();
        Node cur=head;
        while(cur!=null){
            map.put(cur,new Node(cur.val));
            cur=cur.next;
        }
        cur=head;
        while(cur!=null){
            Node bro=map.get(cur);
            //注意这里指向的依旧是bro链表的
            bro.next=map.get(cur.next);
            bro.random=map.get(cur.random);
            cur=cur.next;
        }
        return map.get(head);
    }
}

class Solution {
    public ListNode sortList(ListNode head) {
        if(head==null||head.next==null) return head;
        ListNode slow=head,fast=head.next;
        while(fast!=null&&fast.next!=null){
            slow=slow.next;
            fast=fast.next.next;
        }
        ListNode mid = slow.next;
        slow.next=null;
        return merge(sortList(head),sortList(mid));
        //这句是核心! 一直递归,
    }
    //合并链表
    public ListNode merge(ListNode a,ListNode b){
        ListNode dummy=new ListNode(0), cur=dummy;
        while(a!=null&&b!=null){
            if(a.val<=b.val){
                cur.next=a;
                a=a.next;
            }else {
                cur.next=b;
                b=b.next;
            }
            cur=cur.next;
        }
        cur.next= a==null?b:a;
        return dummy.next;
    }
}

class LRUCache {
    class Node{
        int key,val;
        Node pre,next;
        public Node(int key,int val){
            this.key=key;
            this.val=val;
        }
    }
    public void insert(Node cur){
        cur.pre=head; cur.next=head.next;
        head.next=cur; cur.next.pre=cur;
    }
    public void remove(Node cur){
        cur.pre.next=cur.next;
        cur.next.pre=cur.pre;
    }
    int capacity;
    Node head,tail;
    Map<Integer,Node>map=new HashMap<>();
    public LRUCache(int capacity) {
        head=new Node(0,0);
        tail=new Node(0,0);
        head.next=tail;
        tail.pre=head;
        this.capacity=capacity;
    }
    public int get(int key) {
        Node cur=map.get(key);
        if(cur==null) return -1;
        remove(cur);
        insert(cur);
        return cur.val;
    }
    public void put(int key, int value) {
        Node cur=map.get(key);
        if(cur!=null){
            cur.val=value;
        remove(cur);
        insert(cur);
            return;
        }
        cur=new Node(key,value);
        insert(cur);
            map.put(key,cur);
        if(map.size()>capacity){
            Node lru=tail.pre;
            remove(lru);
            map.remove(lru.key);
        }
    }
}

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        ListNode dummy=new ListNode(0), cur=dummy;
        PriorityQueue<ListNode> minq=new PriorityQueue<>((a,b)->a.val-b.val);
        for(ListNode head:lists){
            //注意offer进去的不能为null
            if(head!=null) minq.offer(head);
        }
        
        while(!minq.isEmpty()){
            ListNode out=minq.poll();
            if(out.next!=null) minq.offer(out.next);
            cur.next=out;
            cur=cur.next;
            cur.next=null;
        }
        return dummy.next;
    }
}

class Solution {

    List<Integer> ans = new ArrayList<>();

    public List<Integer> inorderTraversal(TreeNode root) {

        Stack<TreeNode> stk = new Stack<>();

        TreeNode cur=root;

        //中序一直往左走, 直到尽头, 放出val再往右

        while(!stk.isEmpty()||cur!=null){

            while(cur!=null){

                stk.push(cur);

                cur=cur.left;

            }

            cur=stk.pop();

            ans.add(cur.val);

            cur=cur.right;

        }

        return ans;

    }

	}

class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) return 0;
        return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
    }
}

class Solution {

    public TreeNode invertTree(TreeNode root) {

        if (root == null) return null;

  
		//先反转
        TreeNode left = invertTree(root.left);

        TreeNode right = invertTree(root.right);

  
		//交叉获得各自反转的结果
        root.left = right;

        root.right = left;
        return root;

    }

}

class Solution {

    public boolean isSymmetric(TreeNode root) {

        if(root==null) return true; //防止后面空指针

        return isSame(root.left,root.right);

    }

  

    public boolean isSame(TreeNode l, TreeNode r){

        if(l==null&&r==null) return true; //都空

        if(l==null||r==null) return false;//亦或空

        if(l.val!=r.val) return false;//不等

        //注意这里是交叉的, 真正的镜像

        return isSame(l.left,r.right)&&isSame(r.left,l.right);

    }

}

class Solution {

    int ans=0;

    public int diameterOfBinaryTree(TreeNode root) {

        dfs(root);

        return ans;

    }

  

    public int dfs(TreeNode root){

        if(root==null) return 0; //null返回一, 否则走下一个return +1

        int l=dfs(root.left);

        int r=dfs(root.right);

        ans=Math.max(ans,r+l);//两条链拼接

        return Math.max(l,r)+1;//选择最长的链+1, 但他实际上始终是单链

    }

}

class Solution {

    List<List<Integer>> ans = new ArrayList<>();

    public List<List<Integer>> levelOrder(TreeNode root) {

        if(root==null) return ans;

        Deque<TreeNode> dq=new ArrayDeque<>();

        dq.offer(root);

        while(!dq.isEmpty()){

            int size=dq.size();

            List<Integer> tmp=new ArrayList<>();

            for(int i=0;i<size;i++){

                TreeNode cur=dq.poll();

                tmp.add(cur.val);

                if(cur.left!=null) dq.addLast(cur.left);

                if(cur.right!=null) dq.addLast(cur.right);

            }

            ans.add(tmp);

        }

        return ans;

    }

}

class Solution {

    public TreeNode sortedArrayToBST(int[] nums) {

        return dfs(nums,0,nums.length-1); //[]闭区间

    }

  

    public TreeNode dfs(int[] nums,int l,int r){

        if(l>r) return null;

        int mid=l+(r-l)/2;

        //mid是root, 所以左右不接触

        TreeNode ls=dfs(nums,l,mid-1);

        TreeNode rs=dfs(nums,mid+1,r);

        return new TreeNode(nums[mid],ls,rs);

    }

}

class Solution {

    long pre = Long.MIN_VALUE;

    public boolean isValidBST(TreeNode root) {

        if(root==null) return true;

        if(!isValidBST(root.left)) return false;

        if(root.val<=pre) return false;

        pre=root.val;

        return isValidBST(root.right);

    }

}

class Solution {

    public int kthSmallest(TreeNode root, int k) {

        Deque<TreeNode> dq=new ArrayDeque<>();

        while(true){

            while(root!=null){

                //注意这里是栈的api, 只有这样后进才能先出, 找到第k小!

                dq.push(root);

                root=root.left;

            }

            root=dq.pop();

            if(--k==0) return root.val;

            root=root.right;

        }

    }

}

class Solution {

    List<Integer> ans=new ArrayList<>();

    public List<Integer> rightSideView(TreeNode root) {

        Deque<TreeNode> dq=new ArrayDeque<>();

        if(root==null) return ans;

        dq.offer(root);

  

        while(!dq.isEmpty()){

            int size=dq.size();

            for(int i=0;i<size;i++){

                TreeNode cur=dq.poll();

                if(cur.left!=null) dq.offer(cur.left);

                if(cur.right!=null) dq.offer(cur.right);

                //每层最后一个就是右视图点!!!!!!!!!!!!!

                if(i==size-1) ans.add(cur.val);

            }

        }

        return ans;

    }

}

class Solution {

    public void flatten(TreeNode root) {

        TreeNode cur=root;

        while(cur!=null){

            //思想就是把根的右边街道左节点的右尽头, 然后继续往右走

            if(cur.left!=null){

                TreeNode pre=cur.left;

                while(pre.right!=null) pre=pre.right;

                pre.right=cur.right;

                cur.right=cur.left;

                cur.left=null;

            }

            cur=cur.right;

        }

    }

}

class Solution {

    //val->index, 便于锁定在中序遍历中根节点的位置

    HashMap<Integer,Integer> inpos=new HashMap<>();

    int[] pre;

    public TreeNode buildTree(int[] preorder, int[] inorder) {

        pre=preorder;

        for(int i=0;i<inorder.length;i++) inpos.put(inorder[i],i);

        //注意[]

        return build(0,preorder.length-1,0,inorder.length-1);

    }

  

    public TreeNode build(int prel,int prer,int inl,int inr){

        if(prel>prer) return null;

        int rootVal=pre[prel], rootInPos=inpos.get(rootVal);

        TreeNode root = new TreeNode(rootVal);

  

        int leftsize=rootInPos-inl;

        //注意看是前序的左子树在何处, 右子树在何处, 在对应里面找边界!

        root.left=build(prel+1,prel+leftsize,inl,rootInPos-1);

        root.right=build(prel+leftsize+1,prer,rootInPos+1,inr);

        return root;

    }

}

class Solution {
    int ans = 0;
    Map<Long, Integer> map = new HashMap<>();

    public int pathSum(TreeNode root, int targetSum) {
        map.put(0L, 1);
        dfs(root, 0L, targetSum);
        return ans;
    }
        //1
 //      / \
  //    2   3
 //    / \
  //  4   5 ,比如到了4, 要回退到2并且去访问右5, 那肯定要删掉当前4
    void dfs(TreeNode root, long sum, int target) {
        if (root == null) return;

        sum += root.val;
        ans += map.getOrDefault(sum - target, 0);

        map.merge(sum,1,Integer::sum); //map.put(sum, map.getOrDefault(sum, 0) + 1);

        dfs(root.left, sum, target);
        dfs(root.right, sum, target);

        map.merge(sum,-1,Integer::sum);
    }
}

class Solution {

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {

        //先确定递归边界去找p/q, 没找到返回null

        if(root==null||root==p||root==q) return root;

  

        //递归找p,q, 看看左右子树有没有

        TreeNode l=lowestCommonAncestor(root.left,p,q);

        TreeNode r=lowestCommonAncestor(root.right,p,q);

        if(l==null) return r; //左边是null, 答案在右

        if(r==null) return l; //右边是null, 答案在左

        //左右都不是null, 说明横跨左右子树, 那只能是root了

        return root;

    }

}

class Solution {

    int ans=Integer.MIN_VALUE;

    public int maxPathSum(TreeNode root) {

        dfs(root);

        return ans;

    }

  

    //递归找到最长的边

    public int dfs(TreeNode root){

        if(root==null) return 0;

  

        int l=dfs(root.left), r=dfs(root.right);

        ans=Math.max(ans,l+r+root.val);

  

        int cur=Math.max(l,r)+root.val;

        return Math.max(0,cur); //注意节点可能是负的, 那么干脆不要!

    }

}

class Solution {

    //1是陆地

    int rows,cols;

    int ans=0;

    public int numIslands(char[][] grid) {

        rows=grid.length;

        cols=grid[0].length;

        for(int i=0;i<rows;i++){

            for(int j=0;j<cols;j++){

                if(grid[i][j]=='1'){

                    dfs(grid,i,j);

                    ans++;

                }

            }

        }

        return ans;

    }

  

    public void dfs(char[][] grid,int i,int j){

        if(i<0||i>=rows||j<0||j>=cols||grid[i][j]!='1') return;

        grid[i][j]='0';

        dfs(grid,i,j+1);

        dfs(grid,i,j-1);

        dfs(grid,i+1,j);

        dfs(grid,i-1,j);

    }

	}

class Solution {

    int ans=0;

    public static int[][] dirs={{-1,0},{0,1},{1,0},{0,-1}};

    public int orangesRotting(int[][] grid) {

        int rows=grid.length, cols=grid[0].length, fresh=0;

        List<int[]> q=new ArrayList<>();

        for(int i=0;i<rows;i++){

            for(int j=0;j<cols;j++){

                if(grid[i][j]==1) fresh++;

                else if(grid[i][j]==2) q.add(new int[]{i,j});

            }

        }

  
  

        while(fresh>0&&!q.isEmpty()){

            ans++;

            List<int[]> tmp=q;

            q=new ArrayList<>();

            for(int[] cur:tmp){

                for(int[] d:dirs){

                    int x=cur[0]+d[0];

                    int y=cur[1]+d[1];

                    if(x<0||y<0||x>=rows||y>=cols||grid[x][y]!=1) continue;

                    grid[x][y]=2; fresh--;

                    q.add(new int[]{x,y});

                }

            }

        }

  

        return fresh>0?-1:ans;

    }

}

class Solution {

    public boolean canFinish(int numCourses, int[][] prerequisites) {

        List<Integer>[] graph = new ArrayList[numCourses];

        for(int i=0;i<numCourses;i++) graph[i]=new ArrayList<>();

  

        //建立邻接表, 便于t出0度节点的后继

        int[] indegree=new int[numCourses];

        for(int[] side:prerequisites){

            int ex=side[1], in=side[0];

            graph[ex].add(in);

            indegree[in]++;

        }

  

        Queue<Integer> que = new LinkedList<>();

        for(int i=0;i<numCourses;i++){

            if(indegree[i]==0) que.offer(i);

        }

  

        int cnt=0;

        while(!que.isEmpty()){

            int u=que.poll();

            cnt++; //T出一节课, cnt++, 最后检验t出的是否等于nc

            for(int v:graph[u]){

                if(--indegree[v]==0) que.offer(v);

            }

        }

        return cnt==numCourses;

    }

}

class Trie {

    class node{

        node[] next=new node[26];

        boolean isEnd;

    }

    node root=new node();

  

    public void insert(String word) {

        node cur=root;

        for(char ch : word.toCharArray()){

            int idx=ch-'a';

            if(cur.next[idx]==null) cur.next[idx]=new node();

            cur=cur.next[idx];

        }

        cur.isEnd=true;

    }

    public boolean search(String word) {

        node cur=root;

        for(char ch:word.toCharArray()){

            int idx=ch-'a';

            if(cur.next[idx]==null) return false;

            cur=cur.next[idx];

        }

        return cur.isEnd;

    }

    public boolean startsWith(String prefix) {

        node cur=root;

        for(char ch : prefix.toCharArray()){

            int idx=ch-'a';

            if(cur.next[idx]==null) return false;

            cur=cur.next[idx];

        }

        return true;

    }

}

class Solution {

    int len;

    List<List<Integer>> ans = new ArrayList<>();

    public List<List<Integer>> permute(int[] nums) {

        len=nums.length;

        List<Integer> path = new ArrayList<>();

        for(int num:nums)  path.add(num);

        dfs(path,0);

        return ans;

    }

  

    public void dfs(List<Integer> path, int start){

        if(start==len){

            ans.add(new ArrayList<>(path)); //这里直接放path会用引用导致元素全都一样??

            return;

        }

  

        for(int i=start;i<len;i++){

            Collections.swap(path,start,i);

            dfs(path,start+1);

            Collections.swap(path,start,i);

        }

    }

}

            dfs(path,start+1);
            Collections.swap(path,start,i);

class Solution {

    List<List<Integer>> ans = new ArrayList<>();

    public List<List<Integer>> subsets(int[] nums) {

        int len=nums.length, limit= 1<<len;

        //遍历每种情况

        for(int i=0;i<limit;i++){

            List<Integer> tmp = new ArrayList<>();

            for(int j=0;j<len;j++){

                if(((1<<j)&i)!=0) tmp.add(nums[j]);

            }

            ans.add(tmp);

        }

  

        return ans;

    }

}

class Solution {

    private int len = 0;

    private List<String> ans = new ArrayList<>();

    private static final String[] MAPPING =

    new String[]{"", "", "abc", "def", "ghi",

    "jkl", "mno", "pqrs", "tuv", "wxyz"};

  

    public List<String> letterCombinations(String digits) {

        len=digits.length();

        char[] nums = digits.toCharArray();

        dfs(0,new char[len],nums);

        return ans;

    }

  

    public void dfs(int i,char[] path,char[] nums){

        if(i==len){

            ans.add(new String(path));

            return;

        }

  

        char[] letters=MAPPING[nums[i]-'0'].toCharArray();

        for(char ch:letters){

            path[i]=ch;

            dfs(i+1,path,nums); //这里为啥直接选 因为是枚举

        }

    }

}

class Solution {

    int tar, len;

    List<List<Integer>> ans = new ArrayList<>();

    int[] cands;

  

    public List<List<Integer>> combinationSum(int[] candidates, int target) {

        tar=target; cands=candidates; len=candidates.length;

        dfs(0,0,new ArrayList<>());

        return ans;

    }

  

    public void dfs(int i,int sum,List<Integer> path){

        if(sum==tar){

            //注意这里不能用path, 不然会一直引用同一份path, 由于最后一句一直是removeLast, 所以会导致没有[] [] []

            ans.add(new ArrayList<>(path));

            return;

        }

		//剪枝
        if (sum > tar || i == len) {

            return;

        }

  
		//这里可选可不选
        for(int j=i;j<len;j++){

            path.add(cands[j]);

            dfs(j,sum+cands[j],path); //注意题目可以重复选当前

            path.removeLast(); //不选当前

        }

    }

}

class Solution {

    List<String> ans = new ArrayList<>();

    public List<String> generateParenthesis(int n) {

        dfs(0,0,n,new char[n*2]);

        return ans;

    }

  

    public void dfs(int l,int r,int limit,char[] path){

        if(r==limit){

            ans.add(new String(path));

            return;

        }

        //左边还没到顶, 则试试

        if(l<limit){

            path[l+r]='(';

            dfs(l+1,r,limit,path);

        }

        //左边比右边多了, 那必须出手

        if(l>r){

            path[l+r]=')';

            dfs(l,r+1,limit,path);

        }

    }

}