剑指Offer 32 - III. 从上到下打印二叉树 III

剑指 Offer 32 - III. 从上到下打印二叉树 III

难度中等55
请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。

例如:
给定二叉树: [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

返回其层次遍历结果：

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

Solution

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        if ( root == null) return new ArrayList<>();
        List<List<Integer>> res = new ArrayList<>();
        Stack<TreeNode> left = new Stack<>();
        Stack<TreeNode> right = new Stack<>();
        left.push(root);
        List<Integer> temp = new ArrayList<>();
        int cur = 1, next = 0;
        boolean trun = true;  // 左为 true，右为 false 
        while (!left.isEmpty() || !right.isEmpty()){
            TreeNode node = trun ? left.pop() : right.pop();
            temp.add(node.val);
            if (!trun){
                if (node.right != null){
                    left.push(node.right); 
                    next ++;
                }
                if (node.left != null){
                    left.push(node.left);
                    next ++;
                }
            } else {
                if (node.left != null){
                    right.push(node.left);
                    next ++;
                }
                if (node.right != null){
                    right.push(node.right);
                    next ++;
                } 
            }
            if ( --cur == 0){
                cur = next;
                next = 0;                
                res.add(temp);
                temp = new ArrayList<>();
                trun = !trun;
            }
        }
        return res;
    }
}