二叉树zigzag层级遍历

如图： 图片.png

返回结果：
[
  [3],
  [20,9],
  [15,7]
]

通过分析，我的解法思路为：
1.先定义两个堆栈，然后将根节点放入堆栈A；
2.每次将不为空的一个栈的内容全部出栈，然后将当前层级下的子节点放入另一个堆栈当中；其中堆栈A读取子节点顺序为先左后右，堆栈B先右后左，保证每相邻层间读取顺序为反；
3.如果堆栈A和B均为空，则表明树已遍历完毕；

以如下二叉树为例：

图片.png 图片.png

代码如下：

public static void main(String[] args) {
        TreeNode node4 = new TreeNode(4);
        TreeNode node5 = new TreeNode(5);
        TreeNode node6 = new TreeNode(6);
        TreeNode node7 = new TreeNode(7);
        TreeNode node2 = new TreeNode(2, node4, node5);
        TreeNode node3 = new TreeNode(3, node6, node7);
        TreeNode node1 = new TreeNode(1, node2, node3);
        
        
        Stack<TreeNode> stack1 = new Stack<>();
        stack1.add(node1);
        zigzagLevelOrder(stack1, new Stack<TreeNode>());
    }
    
    private static void zigzagLevelOrder(Stack<TreeNode> stack1, Stack<TreeNode> stack2) {
        while(!stack1.isEmpty() || !stack2.isEmpty()) {         
            while(!stack1.isEmpty()) {
                TreeNode tn = stack1.peek();
                System.out.print(tn.value+"、");
                // 从左往右遍历子节点
                if (tn.left != null) {
                    stack2.push(tn.left);
                }
                if (tn.right != null) {
                    stack2.push(tn.right);
                }
                stack1.pop();
            }
            System.out.println();
            
            while(!stack2.isEmpty()) {
                TreeNode tn = stack2.peek();
                System.out.print(tn.value+"、");
                // 从右往左遍历子节点
                if (tn.right != null) {
                    stack1.push(tn.right);
                }
                if (tn.left != null) {
                    stack1.push(tn.left);
                }
                stack2.pop();
            }
            System.out.println();
        }
    }

该算法引入了堆栈，一共需要额外存储n个空间备份，故空间复杂度为o(n)，时间复杂度也为o(n)。