leetcode103- 二叉樹的鋸齒形層序周遊

一.題目描述

給定一個二叉樹，傳回其節點值的鋸齒形層序周遊。（即先從左往右，再從右往左進行下一層周遊，以此類推，層與層之間交替進行）。

例如：

給定二叉樹 [3,9,20,null,null,15,7],

3
           

/

9 20

/

15 7

傳回鋸齒形層序周遊如下：

[

[3],

[20,9],

[15,7]

]

二.題目解析

這個題目實際上是leetcode102題的變形：

https://blog.csdn.net/xun_zhao_t521/article/details/119879199

稍作修改即可

public List<List<Integer>> zigzagLevelOrder1(TreeNode root) {
         /*疊代-廣度優先搜尋
         利用隊列的先進先出特性層序周遊，儲存結果的時候起到“鋸齒形層次周遊的效果”
         時間複雜度O(n),空間複雜度O(n)
         * */
        if (root == null)
            return new ArrayList<>();
        List<List<Integer>> res = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        //queue 初始時為 [root] ，代表第 1 層
        queue.add(root);
        int flag = 1;
        while (!queue.isEmpty()) {
            //關鍵：count儲存要處理的這一層的節點個數
            int count = queue.size();
            //list儲存此層的所有節點值
            List<Integer> list = new ArrayList<Integer>();
            //這個while循環保證已處理的舊層的節點全部出去，待處理的新層節點全部進入
            while (count > 0) {
                //目前層的節點逐個出列
                TreeNode node = queue.poll();
                //根據層次來判斷順序
                //如果這一層是奇數層就正序插入
                if(flag % 2 == 1){
                    list.add(node.val);
                }else {
                    //如果這一層是偶數層就采用頭插法
                    list.add(0,node.val);
                }
                //存在左孩子則左孩子進隊列（下層節點）
                if (node.left != null)
                    queue.add(node.left);
                //存在右孩子則右孩子進隊列（下層節點）
                if (node.right != null)
                    queue.add(node.right);
                count--;
            }
            flag++;
            res.add(list);
        }
        return res;
    }
           

2.

public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
         /*遞歸··深度優先搜尋
         時間複雜度O(n),空間複雜度O(h)（二叉樹高度）
         * */
        if (root == null) {
            return new ArrayList<List<Integer>>();
        }
        //用來存放最終結果
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        dfs(1, root, res);
        return res;
    }

    void dfs(int index, TreeNode root, List<List<Integer>> res) {
         /*遞歸函數定義，層序周遊以root為根的二叉樹的節點（root處于第index層）
         儲存結果的時候起到“鋸齒形層次周遊的效果”
         * */
        //假設res是[ [1],[2,3] ]， index是3，就再插入一個空list放到res中
        if (res.size() < index) {
            res.add(new ArrayList<Integer>());
        }
        //1.先把root節點值添加到res[index-1]數組裡
        //将目前節點的值加入到res中，index代表目前層，假設index是3，節點值是99
        //res是[ [1],[2,3] [4] ]，加入後res就變為 [ [1],[2,3] [4,99] ]
        //如果這一層是奇數層
        if(index % 2 == 1){
            res.get(index - 1).add(root.val);
        }else {
            //如果這一層是偶數層就采用頭插法
            res.get(index - 1).add(0,root.val);
        }
        //2.再遞歸的處理左子樹，右子樹，同時将層數index+1
        if (root.left != null) {
            dfs(index + 1, root.left, res);
        }
        if (root.right != null) {
            dfs(index + 1, root.right, res);
        }
    }