LeetCode：103. Binary Tree Zigzag Level Order Traversal

本文为LeetCode：103. Binary Tree Zigzag Level Order Traversal的题解。

题意

一颗给定的二叉树，返回节点值的之子形的便利结果。即，从左到右，然后下一级别是从右到左，如此交替。

例如：

给定二叉树：[3,9,20,null,null,15,7]：

  3
 / \
9  20
  /  \
 15   7

程序将会返回之字形遍历顺序：

[
  [3],
  [20,9],
  [15,7]
]

题解

对于第一层遍历，从左到右，添加到一个stack中；对于第二层遍历，pop出来的顺序是从右到左，所以要额外考虑先添加right子节点、再添加left子节点到stack中。

代码

import java.util.*;

/**
 * https://www.robberphex.com/binary-tree-zigzag-level-order-traversal/
 */
class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> levelTraversal = new ArrayList<>();
        if (root == null) {
            return levelTraversal;
        }

        // 第level级的节点存储在curLevel中
        int level = 0;
        Stack<TreeNode> curLevel = new Stack<>();
        curLevel.push(root);

        // 存储下一级节点
        Stack<TreeNode> nextLevel = new Stack<>();

        while (!curLevel.isEmpty()) {
            // 遍历当前层的节点
            List<Integer> traversal = new ArrayList<>();
            while (!curLevel.isEmpty()) {
                TreeNode cur;
                // 对于顺向层，pop是从左到右
                // 对于逆向层，pop是从右到左
                cur = curLevel.pop();
                if (cur == null) {
                    continue;
                }
                if (level % 2 == 1) {
                    nextLevel.push(cur.right);
                    nextLevel.push(cur.left);
                } else {
                    nextLevel.push(cur.left);
                    nextLevel.push(cur.right);
                }
                traversal.add(cur.val);
            }
            if (!traversal.isEmpty()) {
                levelTraversal.add(traversal);
            }
            level++;
            curLevel = nextLevel;
            nextLevel = new Stack<>();
        }

        return levelTraversal;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.right.right = new TreeNode(5);
        List<List<Integer>> res = new Solution().zigzagLevelOrder(root);
        System.out.println(res);
        // 输出 [[1], [3, 2], [4, 5]]
    }
}