12.4 剑指Offer 41-59

2020-08-10  本文已影响0人  AlexLJS

41、

public class FindContinuousSequence_41 {
    /**
     * 和为s的连续正数序列
     *
     * 题目描述
     * 小明很喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,
     * 他马上就写出了正确答案是100。但是他并不满足于此,
     * 他在想究竟有多少种连续的正数序列的和为100(至少包括两个数)。
     * 没多久,他就得到另一组连续正数和为100的序列:18,19,20,21,22。
     * 现在把问题交给你,你能不能也很快的找出所有和为S的连续正数序列? Good Luck!
     */

    public ArrayList<ArrayList<Integer>> FindContinuousSequence(int sum) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();

        int l = 1;

        while (l <= sum>>1){
            int d = 1;
            while ( (2*l + d) * (d + 1) <= 2 * sum){
                System.out.println((2*l + d) * (d + 1));
                if ((2*l + d) * (d + 1) == 2 * sum){
                    ArrayList<Integer> temp = new ArrayList<>();
                    for (int i = l; i <= l+d; i++) {
                        temp.add(i);
                    }
                    res.add(temp);
                    break;
                }else {
                    d++;
                }
            }
            l++;
        }
        return res;
    }

}


42、

public class FindNumbersWithSum_42 {
    /**
     * 和为s的两个数
     *
     * 题目描述
     * 输入一个递增排序的数组和一个数字S,在数组中查找两个数,
     * 使得他们的和正好是S,如果有多对数字的和等于S,输出两个数的乘积最小的。
     *
     * 思路:
     * 遍历到sum >> 1 。 每一个数a都在后半数组二分查找 sum - a 。
     *
     */

    public ArrayList<Integer> FindNumbersWithSum(int [] array, int sum) {
        ArrayList<Integer> res = new ArrayList<>();
        for (int i = 0; array.length > 1 && i <= array.length >> 1; i++) {
            int a = array[i];
            int l = i + 1;
            int r = array.length - 1;

            while (l <= r){
                int mid = (l + r) >> 1;
                if (array[mid] == sum - a){
                    res.add(a);
                    res.add(array[mid]);
                    return res;
                }else if (array[mid] > sum - a){
                    r = mid - 1;
                }else {
                    l = mid + 1;
                }
            }
        }
        return res;
    }

}

43、

public class LeftRotateString_43 {
    /**
     * 左旋字符串
     *
     * 题目描述
     * 汇编语言中有一种移位指令叫做循环左移(ROL),现在有个简单的任务,
     * 就是用字符串模拟这个指令的运算结果。对于一个给定的字符序列S,
     * 请你把其循环左移K位后的序列输出。例如,字符序列S=”abcXYZdef”,
     * 要求输出循环左移3位后的结果,即“XYZdefabc”。是不是很简单?OK,搞定它!
     *
     * 思路 ;
     * substring 可以一行代码 return str.substring(n) + str.substring(0,n);
     *
     * 这肯定不是要考察的。空间复杂度On。考查问题划分为子问题,
     * 通过多次翻转达到最终效果。
     */
    public  String LeftRotateString(String str,int n) {
        int len = str.length();
        if (len == 0) return "";
        n %= len;
        char[] chars = str.toCharArray();
        rotate(chars, 0, n - 1);
        rotate(chars, n, len - 1);
        rotate(chars, 0, len - 1);

        return new String(chars);
    }

    private void rotate(char[] chars, int l, int r){
        while (l < r){
            char temp = chars[l];
            chars[l] = chars[r];
            chars[r] = temp;
            l++;
            r--;
        }
    }

}

44、

public class ReverseSentence_44 {
    /**
     * 反转单词序列
     *
     *题目描述
     * 牛客最近来了一个新员工Fish,每天早晨总是会拿着一本英文杂志,
     * 写些句子在本子上。同事Cat对Fish写的内容颇感兴趣,有一天他向Fish借来翻看,但却读不懂它的意思。
     * 例如,“student. a am I”。后来才意识到,
     * 这家伙原来把句子单词的顺序翻转了,正确的句子应该是“I am a student.”。
     * Cat对一一的翻转这些单词顺序可不在行,你能帮助他么?
     *
     * 思路 :
     * 推荐解法 : 先转整个句子再转单词.
     *
     * 思路2 : 也可以将字符串按' ' 截断 ,存到数组中,反向拼接
     */
    public String ReverseSentence(String str) {
        int len = str.length();
        if (len == 0) return "";
        char[] chars = str.toCharArray();
        int i = 0;
        while (i < len){
            int j = i + 1;
            while (j < len && chars[j] != ' ') j++;
            rotate(chars, i, j - 1);
            i = j + 1;
        }
        rotate(chars, 0 , len-1);
        return new String(chars);
    }

    private void rotate(char[] chars, int l, int r){
        while (l < r){
            char temp = chars[l];
            chars[l] = chars[r];
            chars[r] = temp;
            l++;
            r--;
        }
    }

}

45、

public class IsContinuous_45 {
    /**
     * 扑克顺子
     *
     * 题目描述
     * LL今天心情特别好,因为他去买了一副扑克牌,发现里面居然有2个大王,
     * 2个小王(一副牌原本是54张^_^)...他随机从中抽出了5张牌,
     * 想测测自己的手气,看看能不能抽到顺子,如果抽到的话,
     * 他决定去买体育彩票,嘿嘿!!“红心A,黑桃3,小王,大王,方片5”,“Oh My God!”不是顺子.....LL不高兴了,他想了想,决定大\小 王可以看成任何数字,并且A看作1,J为11,Q为12,K为13。
     * 上面的5张牌就可以变成“1,2,3,4,5”(大小王分别看作2和4),“So Lucky!”。LL决定去买体育彩票啦。
     *
     * 现在,要求你使用这幅牌模拟上面的过程,然后告诉我们LL的运气如何,
     * 如果牌能组成顺子就输出true,否则就输出false。
     * 为了方便起见,你可以认为大小王是0。
     *
     * 思路:
     * 判断0 的个数,算根据最大值与最小值的差讨论
     */
    public boolean isContinuous(int [] numbers) {
        if (numbers.length < 5) return false;
        Arrays.sort(numbers);
        int lastZero = -1;
        for(int i = 0; i < 5; i++){
            if (numbers[i] == 0) {
                lastZero++;
                continue;
            }
            if (i > 0 && numbers[i] == numbers[i-1]) return false;
        }

        if (numbers[0] == 0){
            if (lastZero == 3){
                return true;
            }else {
                if (numbers[4] - numbers[lastZero + 1] <= 4) return true;
            }
        }else{
            if (numbers[4] - numbers[0] == 4) return true;
        }
        return false;
    }
}

46、

public class LastRemaining_46 {
    /**
     *
     * 孩子们的游戏
     *
     * 找到最后剩下的人
     *
     * @param n 人数
     * @param m 查询次数
     * @return 最终下标
     *
     * 思路:
     * 经典约瑟夫环问题 。 
     * 寻找移除元素前后, 下标之间的关系。利用递推公式,写出递归函数。
     *(f(n,m)表示 当前 n 个人,移除第m个人下标)
     * 0 1 2 3 ... n-1
     * 0 ... m-1 ... n-1
     * 移除 f(n-1,m) , 移除第m个人,索引是 m-1
     * 0..m-1,m,m+1..n-1
     * 从m开始重新编号(m-1已移除)
     *        0 1 2 ... n-2 子问题变成 在 n-1个人中移除第m个人
     * 这次移除结果的下标, f(n-1,m) 与 f(n,m) 之间 存在映射关系, ( f(n-1,m) + m )%n = f(n , m)
     */

    public int LastRemaining_Solution(int n, int m) {
        if (m <= 0) return -1;
        if (n == 0) return -1;
        if (n == 1) {
            return 0;
        }else {
            return (m + LastRemaining_Solution(n - 1, m))%n;
        }
    }
}

47、

public class Sum_47 {
    /**
     * 求 1 到 n 的和
     *
     * 题目描述
     * 求1+2+3+...+n,要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句(A?B:C)。
     *
     * 思路
     * 用短路性质, 代替if语句, 用递归代替while循环
     *
     * 这个属于脑筋急转弯
     */

    public int Sum_Solution(int n) {
        int sum = n;
        boolean t = n > 0 && (sum += Sum_Solution(n-1)) != -1;
        return sum;
    }
}

48、

public class Add_48 {
    /**
     * 求两个整数之和
     *
     * 题目描述
     * 写一个函数,求两个整数之和,要求在函数体内不得使用+、-、*、/四则运算符号。
     *
     * 思路:
     * 计算机 底层原理, + 运算的实现。
     *
     * ^ 异或操作,实现 不进位加法
     * & 位与操作,实现 统计进位 << 1
     *
     * 不能使用+ , 所用 num2 记录 carry进位, 用num1记录和, 循环处理 进位之后再进位
     */
    public int Add(int num1,int num2) {
        while (num2 != 0){
            int temp = num2;
            num2 = (num1 & num2) << 1;
            num1 = num1 ^ temp;
        }
        return num1;
    }
}

49、

public class StrToInt_49 {
    /**
     * 把字符串转成整数
     *题目描述
     * 将一个字符串转换成一个整数,要求不能使用字符串转换整数的库函数。 数值为0或者字符串不是一个合法的数值则返回0
     * 输入描述:
     * 输入一个字符串,包括数字字母符号,可以为空
     * 输出描述:
     * 如果是合法的数值表达则返回该数字,否则返回0
     *
     * 思路: 根据asc码分类讨论
     *
     */
    public int StrToInt(String str) {
        // ASCII [48,57] [0,9] ;  [0] space ; 43 + ; 45 -

        char[] ary = str.toCharArray();
        long res = 0;
        int e = 0;
        int sign = 1;

        for(int i = ary.length - 1; i >= 0; i--){
            if (ary[i] == 0) continue;
            if (ary[i] >= 48 && ary[i] <= 57){
                res += Math.pow(10,e) * ( ary[i] - 48);
            }else{
                if (i == 0 && ary[i] == 45) {
                    sign = -1;
                    break;
                }
                if (i == 0 && ary[i] == 43) break;
                return 0;
            }
            e++;
        }
        res = res * sign;
        if (res > Integer.MAX_VALUE) return Integer.MAX_VALUE;
        if (res < Integer.MIN_VALUE) return Integer.MIN_VALUE;
        return (int) res;
    }
}

50、

public class FindDuplicate_50 {
    /**
     *  数组中重复的数
     *
     * 题目描述
     * 在一个长度为n的数组里的所有数字都在0到n-1的范围内。
     * 数组中某些数字是重复的,但不知道有几个数字是重复的。
     * 也不知道每个数字重复几次。请找出数组中任意一个重复的数字。
     *
     * 例如,如果输入长度为7的数组{2,3,1,0,2,5,3},
     * 那么对应的输出是第一个重复的数字2。
     *
     * 思路:
     * 首先时间复杂度肯定是O(N), 至少要遍历一遍数组,重点应该放在空间复杂度上。
     * 最简单思路肯定是 哈希表。这样就没有用到已知条件n和n-1关系
     *
     * 由已知,得没重复的情况下标i与元素num[i]应该是一一对应的。
     * 那我们遍历数组时,每次考虑将i索引的值num[i]放到索引 num[i]的位置。
     * 如果i已经在num[i]位置,要跳过; 要换的位置dest上已经有匹配的数了,就返回。
     *
     */
    // Parameters:
    //    numbers:     an array of integers
    //    length:      the length of array numbers
    //    duplication: (Output) the duplicated number in the array number,length of duplication array is 1,so using duplication[0] = ? in implementation;
    //                  Here duplication like pointor in C/C++, duplication[0] equal *duplication in C/C++
    //    这里要特别注意~返回任意重复的一个,赋值duplication[0]
    // Return value:       true if the input is valid, and there are some duplications in the array number
    //                     otherwise false

    public boolean duplicate(int numbers[],int length,int [] duplication) {

        for (int i = 0; i < length; i++) {
            if (numbers[i] > length-1 || numbers[i] < 0) {
                duplication[0] = -1;
                return false;
            }
            //正确位置的数不需要交换
            if (numbers[i] != i && !sSwap(numbers, i)){
                duplication[0] = numbers[i];
                return true;
            }
        }
        duplication[0] = -1;
        return  false;
    }
    //将 i 放到正确的位置
    private boolean sSwap(int[] arr, int i){
       int dest = arr[i];
       if (dest == arr[dest]) {
           return false;//放入失败,已找到重复元素
       } else {
           int temp = arr[i];
           arr[i] = arr[dest];
           arr[dest] = temp;
       }
       return true;
    }
    /**
     *  进阶
     *  数据范围 1-n
     *  数组长度 n+1
     *  根据抽屉原理至少有一个重复的数
     *  例如 n = 4 , [2,3,1,4,2]
     *
     *  要求: 不改变数组结构,不能使用额外空间,找出一个重复的数
     *
     *  思路:二分值域,一遍一遍统计值域内数据个数,时间复杂度 NlogN
     *  例如 4 -> [1,2] 内有3个 , [3,4]内有2个数
     *
     *  由于限制空间复杂度,无法使用递归
     */


    public int pro(int[] arr){
        int len = arr.length;
        int n = len - 1;
        int l = 1;
        int r = n;

        while (l < r){
            int mid = (l + r)>>1;
            int count = 0;

            for (int e:arr
                 ) {
                if (e >= l && e <= mid) count++;
            }
            // [l,mid] [mid + 1 , r]
            if (count > mid - l + 1) {
                r = mid;
            }else {
                l = mid + 1;
            }
        }
        //l r是数组值域,return arr[r] 调了半天,哎
        return r;
    }
}

51、

public class Multiply_51 {
    /**
     * 构建乘积数组
     *
     * 题目描述
     * 给定一个数组A[0,1,...,n-1],请构建一个数组B[0,1,...,n-1],
     * 其中B中的元素B[i]=A[0]*A[1]*...*A[i-1]*A[i+1]*...*A[n-1]。不能使用除法。
     * (注意:规定B[0] = A[1] * A[2] * ... * A[n-1],B[n-1] = A[0] * A[1] * ... * A[n-2];)
     * 对于A长度为1的情况,B无意义,故而无法构建,因此该情况不会存在。
     *
     * 思路 :
     * 维护两个数组 [ai]表示 0~i-1 的乘积,[bi]表示 i+1 ~ 0 的乘积。
     * 这样用了两个数组。
     * 将这两个数组 优化成一个 结果数组 + 一个变量。
     */

    public int[] multiply(int[] A) {

        int[] res = new int[A.length];
        res[0] = 1;
        for (int i = 1; i < A.length; i++) {
            res[i] = res[i-1] * A[i-1];
        }
        int temp = 1;
        for (int i = A.length - 2; i >= 0 ; i--) {
            temp *= A[i + 1];
            res[i] *= temp;
        }

        return res;
    }
    
}

52、

public class Match_52 {
    /**
     * 正则表达式的匹配
     *
     * 题目描述
     * 请实现一个函数用来匹配包括'.'和'*'的正则表达式。
     * 模式中的字符'.'表示任意一个字符,而'*'表示它前面的字符可以出现任意次(包含0次)。
     * 在本题中,匹配是指字符串的所有字符匹配整个模式。例如,字符串"aaa"与模式"a.a"和"ab*ac*a"匹配,
     * 但是与"aa.a"和"ab*a"均不匹配
     *
     * 思路:
     * 经典动态规划,很难,做不出来。建议背下来。
     *  s 字符串 , p 模式串
     *  dp[i][j] 表示 s 第 i 位开始能和 p 的 j 位之后的模式串匹配。
     *
     *  状态转移 : 分情况讨论
     *
     *  1) p[j] 是正常字符 , i、j 为相同字符
     *
     *  dp[i][j] = (s[i] = p[j]) && dp[i+1][j+1]
     *
     *  2) p[j] 是 . s[i] 是任意字符
     *
     *  dp[i][j] = dp[i+1][j+1]
     *
     *  3) p[j+1] 是 *, 再次分情况谈论 :
     *  * 代表 0,那么p串等于直接少两位
     * 如果*不代表0 , p[j]至少有一个 , 所以p[j] 与 s[i]匹配,因为状态dp[i+1][j]包含了*为0的情况,可以直接依赖这个状态。
     *
     *  dp[i][j] =  dp[i][j+2] || (p[j] == s[i] && dp[i+1][j])
     *
     */

    public boolean match(char[] str, char[] pattern)
    {
        int m = str.length;
        int n = pattern.length;
        boolean[][] dp = new boolean[m + 1][n + 1];
        //初始值 可以匹配
        dp[m][n] = true;
        for (int i = m ; i >= 0; i--) {
            for (int j = n - 1; j >= 0 ; j--) {
                boolean curMatch = (i < m && (pattern[j] == str[i] || pattern[j] == '.'));

                if (j + 1 < n && pattern[j+1] == '*'){
                    dp[i][j] = dp[i][j+2] || curMatch && dp[i+1][j];
                } else {
                    dp[i][j] = curMatch && dp[i+1][j+1];
                }

            }
        }
        return dp[0][0];
    }

}

53、

public class IsNumeric_53 {
    /**
     * 表示数字的字符串
     *
     * 题目描述
     * 请实现一个函数用来判断字符串是否表示数值(包括整数和小数)。
     * 例如,字符串"+100","5e2","-123","3.1416"和"-1E-16"都表示数值。
     * 但是"12e","1a3.14","1.2.3","+-5"和"12e+4.3"都不是。
     *
     * 思路:
     * 分情况讨论问题,没有什么算法内容。 可以用正则表达式偷鸡。
     *
     * step1 :
     *  前后空格删除
     *
     *  step2 :
     *  +-号摘除
     */
    public boolean isNumeric(char[] str) {

        String input = new String(str);
        //String pattern = "^[\\+\\-]?\\d*(\\.\\d+)?([eE][\\+\\-]?\\d+)?$";
        String pattern = "^[+-]?([0-9]+(\\.[0-9]*)?|\\.[0-9]+)([eE][+-]?[0-9]+)?$";

        boolean isMatch = Pattern.matches(pattern, input);

        Pattern p = Pattern.compile(pattern);
        Matcher m = p.matcher("23");


        return isMatch;
    }
}

54、

public class FirstAppearingOnce_54 {
    /**
     * 字符流中只出现一次的字符
     *
     * 题目描述
     * 请实现一个函数用来找出字符流中第一个只出现一次的字符。
     * 例如,当从字符流中只读出前两个字符"go"时,第一个只出现一次的字符是"g"。
     * 当从该字符流中读出前六个字符“google"时,第一个只出现一次的字符是"l"。
     *
     * 输出描述:
     * 如果当前字符流没有存在出现一次的字符,返回#字符。
     *
     * 思路 :
     * 第一次,使用数组下标映射char, 形成哈希表。 int[256]
     * 二刷时,感觉解法通用性比较差,换成了单调队列。
     *
     * 用map统计字符入队列次数, 队列头部保存出现一次的char。
     * 每次出队列的时候校验,map中队头是否只出现过一次。
     * true return, false 出队列,判断队列头的下一个元素。
     */

    HashMap<Character,Integer> map = new HashMap<>();
    LinkedList<Character> queue = new LinkedList<>();

    //Insert one char from stringstream
    public void Insert(char ch)
    {
        if (map.containsKey(ch)){
            map.put(ch,map.get(ch) + 1);
        }else {
            map.put(ch, 1);
        }

        queue.add(ch);
    }
    //return the first appearence once char in current stringstream
    public char FirstAppearingOnce()
    {
        while (!queue.isEmpty()){
            if ( map.get(queue.peek()) == 1) {
                return queue.peek();
            }else {
                queue.poll();
            }
        }
        return '#';
    }
}

55、

public class EntryNodeOfLoop_55 {
    /**
     *
     * 环形链表入口节点
     *
     * 题目描述
     * 给一个链表,若其中包含环,请找出该链表的环的入口结点,否则,输出null。
     *
     * 思路:
     * 这是一个经典的双指针问题,数学方法可以证明结论的正确性。
     *  fast 走两步, low 走一步, fast终将在环上与low 相遇。
     *  相遇的以后,fast 每次走一步,从头开始走。
     *  再次相遇就是入口节点。
     *
     * 注意处理边界情况。
     */

    public ListNode EntryNodeOfLoop(ListNode pHead)
    {
        ListNode fast = pHead;
        ListNode low = pHead;

        // fast next 边界越界
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            low = low.next;

            if (fast == low){
                while (pHead != low){
                    pHead = pHead.next;
                    low = low.next;
                }
                return low;
            }

        }

        return null;
    }

}

56、

public class DeleteDuplication_56 {
    /**
     * 删除重复节点
     *
     * 题目描述
     * 在一个排序的链表中,存在重复的结点,请删除该链表中重复的结点,重复的结点不保留,返回链表头指针。
     * 例如,链表1->2->3->3->4->4->5 处理后为 1->2->5
     *
     * 思路:
     * 经典双指针问题。很绕。
     *
     * a表示 结果链表的尾节点 , b表示扫描指针。
     * b找到第一个跟 a.next 值不同的节点,b 是 a.next.next的话,证明a.next 是唯一节点否则放弃。
     *
     */


    public static ListNode deleteDuplication(ListNode pHead)
    {
        ListNode dummy = new ListNode(Integer.MAX_VALUE);
        dummy.next = pHead;
        ListNode a = dummy;
        ListNode b = pHead;

       while (a.next != null){
           while ( b != null &&  a.next.val == b.val){
               b = b.next;
           }
           if (a.next.next == b){
               a = a.next;
           }else {
               a.next = b;
           }
       }

       return dummy.next;
    }


}

57、

public class GetNext_57 {
    /**
     * 二叉树的下一个节点
     *
     * 题目描述
     * 给定一个二叉树和其中的一个结点,请找出中序遍历顺序的下一个结点并且返回。
     * 注意,
     * 树中的结点不仅包含左右子结点,同时包含指向父结点的指针。
     *
     * 思路:
     * 经典题目 俗称 “树的后继”
     * 这里的树的结构有变化, 给出的父节点next。
     * 核心思路就是 分类讨论, 节点左子树全部不用考虑,如有有右子树,那么下一个节点一定在右子树
     * 如果没有右子树,那么下一个节点是不是父节点呢? 如果节点是next 的左孩子,
     * 那么后继就是next, 如果是右孩子说明next已经被遍历过了, 找父节点的父节点。
     */

    public TreeLinkNode GetNext(TreeLinkNode pNode)
    {
        TreeLinkNode cur = pNode;

        if (cur.right != null){
            cur = cur.right;
            while (cur.left != null) cur = cur.left;
            return cur;
        }

        while (cur.next != null){
            if (cur.next.left == cur) return cur.next;
            cur = cur.next;
        }

        return null;
    }

}

58、

public class IsSymmetrical_58 {
    /**
     *
     * 对称的二叉树
     *
     * 题目描述
     * 请实现一个函数,用来判断一棵二叉树是不是对称的。
     * 注意,如果一个二叉树同此二叉树的镜像是同样的,定义其为对称的。
     *
     * 思路:
     * 很多种思路啊, 层序遍历熟悉可以层序遍历 判断层是否是回文;
     * 也可以, 相反过程 process1 找左孩子, process2 找右边孩子, 不相等就不是对称。
     *
     * 把第二种思路写成递归过程。
     */

    boolean isSymmetrical(TreeNode pRoot)
    {
        if (pRoot == null) return true;
        return process(pRoot.left, pRoot.right);
    }


    private boolean process(TreeNode left, TreeNode right){
        //特例判断巧妙
        if (left == null || right == null) return right == null && left == null;
        if (left.val != right.val) return false;
        return process( left.right, right.left) && process( left.left, right.right);
    }
}

59、

public class ZigPrintBinaryTree_59 {
    /**
     * 之字形打印二叉树
     *
     *
     * 题目描述
     * 请实现一个函数按照之字形打印二叉树,即第一行按照从左到右的顺序打印,
     * 第二层按照从右至左的顺序打印,第三行按照从左到右的顺序打印,其他行以此类推。
     *
     * 思路:
     * 考查二叉树的层序遍历, 偶数行从右到左输出。 用 flag 标记输出方向。
     *
     * 注 : 不要尝试用LinkedList双向链表,改变双向链表指针,八成是要绕懵逼。
     */

    public ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        if (pRoot == null) return res;

        Queue<TreeNode> queue = new LinkedList<>();//linkedList 双向链表不能使用 Queue接口
        ArrayList<Integer> floor = new ArrayList<>();
        TreeNode mark = new TreeNode(Integer.MAX_VALUE);//换行标志
        boolean flag = true; // true : left -> right

        queue.add(pRoot);
        queue.add(mark);

        while (!queue.isEmpty()){
            TreeNode temp = queue.poll();
            if (temp == mark){
                if (!flag)Collections.reverse(floor);
                res.add(floor);
                flag = !flag;
                floor = new ArrayList<>();
                if (queue.isEmpty()) break;
                queue.add(mark);
                continue;
            }
            floor.add(temp.val);
            if (temp.left != null) queue.add(temp.left);
            if (temp.right != null) queue.add(temp.right);
        }

        return res;
    }
}

上一篇 下一篇

猜你喜欢

热点阅读