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;
	}

}