LeetCode103二叉樹的鋸齒形層次周遊(相關話題：二叉樹、層次周遊)

題目描述

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

例如：

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

    3

   / \

  9  20

    /  \

   15   7

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

[

  [3],

  [20,9],

  [15,7]

]

解題思路

首先定義 cnt 來記錄層數的奇偶性，然後在每層結點出隊時判斷一下該層的奇偶性再存入數組

如果是偶數層就正向存儲（以 0 為起始層），奇數層則反向存儲

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> ans = new ArrayList<>();
        if (root == null) {
            return ans;
        }
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        // 記錄層數的奇偶性
        int cnt = 0;
        while (!q.isEmpty()) {
            List<Integer> tmp = new ArrayList<>();            
            int len = q.size();
            //每個for對應二叉樹的一層
            for (int i = 0; i < len; i++) {
                TreeNode node = q.poll(); 
                // 這裡将層數的奇偶性做下判斷
                // 如果是偶數層就正向存儲（以 0 為起始層）
                if (cnt % 2 == 0) {
                    tmp.add(node.val);
                } else {
                    // 奇數層則反向存儲
                    tmp.add(0, node.val);
                }
                
                if (node.left != null) {
                    q.add(node.left);
                }
                if (node.right != null) {
                    q.add(node.right);
                }
            }
            cnt++;
            ans.add(tmp);
        }
        return ans;
    }
}
           

class Solution {

    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
		List<List<Integer>> ans = new ArrayList<>();

		return levelOrder(ans,root,1);
    }

    public List<List<Integer>> levelOrder(List<List<Integer>> ans, TreeNode root, Integer level) {

		if (root == null) {
			return ans;
		}

        //進入新層次時需要新起一個list放到ans裡
		List<Integer> temp = null;
		if (level > ans.size()) {
			temp = new ArrayList<>();
			ans.add(temp);
		}

		temp = ans.get(level - 1);

		if (level % 2 == 1) {
			temp.add(root.val);
		} else {
			// 偶數層需要逆向插入
			temp.add(0, root.val);
		}

		if (root.left != null) {
			levelOrder(ans, root.left, level + 1);
		}
		if (root.right != null) {
			levelOrder(ans, root.right, level + 1);
		}

		return ans;
	}

}