class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if(root == null) return res;
        LinkedList<TreeNode> list = new LinkedList<>();
        list.add(root);
        while(!list.isEmpty()){
            int size = list.size();
            List<Integer> l = new ArrayList<>();
            for(int i = 0;i < size;i++){
                TreeNode t = list.pop();
                l.add(t.val);
                if(t.left != null)list.add(t.left);
                if(t.right != null)list.add(t.right);
            }
            res.add(l);
        }
        return res;
    }
}

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        fun(root,list);
        return list;
    }
    public void fun(TreeNode root,List<Integer> list){
        if(root == null)return;
        fun(root.left,list);
        list.add(root.val);
        fun(root.right,list);
    }
}

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if(root == null) return list;
        Stack<TreeNode> stack = new Stack<>();
        while(root != null || !stack.isEmpty()){
            while(root != null){
                stack.add(root);
                root = root.left;
            }
            TreeNode node = stack.pop();
            list.add(node.val);
            root = node.right;
        }
        return list;
    }
}

class Solution {
    public String minWindow(String s, String t) {
        int slen = s.length();
        int tlen = t.length();
        if(slen < tlen) return "";
        int res = slen + 1;
        int left = 0;
        char [] arrs = s.toCharArray();
        char [] arrt = t.toCharArray();
        int [] s1 = new int[128];
        int [] t1 = new int[128];
        for(int i = 0;i < tlen;i++){
            t1[arrt[i]]++;
        }
        for(int i = 0;i < slen;i++){ // 枚举起始位置
            Arrays.fill(s1,0);
            for(int j = i;j < slen;j++){ // 枚举结束位置
                s1[arrs[j]]++;
                if(j-i+1 < tlen) continue;
                if(check(s1,t1)){
                    System.out.println(i+" "+j);
                    if(res > j-i+1){
                        res = j-i+1;
                        left = i;
                    }
                    break;
                }
            }
        }
        if(res == slen+1) return "";
        StringBuilder sb = new StringBuilder();
        for(int i = left;i < left+res;i++){
            sb.append(arrs[i]);
        }
        return sb.toString();
    }
    public boolean check(int[] arrs,int[] arrt){
        for(int i = 0;i < arrs.length;i++){
            if(arrs[i] < arrt[i]){
                return false;
            }
        }
        return true;
    }
}

class Solution {
    public String minWindow(String s, String t) {
        int slen = s.length();
        int tlen = t.length();
        if(slen < tlen) return "";
        int minLen = slen + 1;
        int begin = 0;
        int left = 0;
        int right = 0;
        int distance = 0;
        char [] arrs = s.toCharArray();
        char [] arrt = t.toCharArray();
        int [] s1 = new int[128];
        int [] t1 = new int[128];
        for(int i = 0;i < tlen;i++){
            t1[arrt[i]]++;
        }
        while(right < slen){   
            //1. 如果当前字符没有在t中
            if(t1[arrs[right]] == 0){
                s1[arrs[right]]++;
                right++;
                continue;
            }
            //2. 到这里说明当前字符在t中存在
            //2.1 当left - right中这个字符的个数少于t1中这个字符个数时候才加一
            // 因为当等于或者大于的时候，说明s1中这个的字符与t1中相等或者大于，但是他实际包含的t1的长度是t1中字符的长度 
            if(s1[arrs[right]] < t1[arrs[right]]){
                distance++;
            }
            s1[arrs[right]]++;
            right++;
            //3.说明找到一个字符串满足条件了,就开始收缩左边界
            while(distance == tlen){
                if(right - left < minLen){
                    minLen = right-left;
                    begin = left;
                }
                if(s1[arrs[left]] == t1[arrs[left]]){
                    distance--;
                }
                s1[arrs[left]]--;
                left++;
            }            
        }
        if(minLen == slen + 1) return "";
        return s.substring(begin,begin+minLen);
    }
}