二叉树的相关习题总结

1.问题描述
给定一个二叉树，返回该二叉树的之字形层序遍历，（第一层从左向右，下一层从右向左，一直这样交替）
例如：
给定的二叉树是{3,9,20,#,#,15,7}

该二叉树之字形层序遍历的结果是

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

题目分析：
可以发现奇数行是从左往右输出，偶数行是从右往左，我们可以采用两个栈的思路解决问题，一个栈对偶数处理，另一个对奇数处理。

public ArrayList<ArrayList<Integer>> zigzagLevelOrder (TreeNode root) {
        // write code here
           if(root==null||root.val==0)return new ArrayList<>();
        Stack<TreeNode> stack=new Stack<>();
        Stack<TreeNode> stack1=new Stack<>();
        ArrayList<ArrayList<Integer>> lists=new ArrayList<>();
        ArrayList<Integer> arrayList=new ArrayList<>();
        //使用stack 奇数行 结果从左往右打印  stack1 偶数行 从右往左打印
        stack.push(root);
        int i=2;
        while (!stack.isEmpty()||!stack1.isEmpty()){
            //偶数行
            if(i%2==0){
                while (!stack.isEmpty()) {
                    TreeNode node = stack.pop();
                    arrayList.add(node.val);
                    if (node.left != null)
                        stack1.push(node.left);
                    if (node.right != null) stack1.push(node.right);
                }

            }else {
                while (!stack1.isEmpty()) {
                    TreeNode node = stack1.pop();
                    arrayList.add(node.val);
                    if (node.right != null) stack.push(node.right);
                    if (node.left != null)
                        stack.push(node.left);
                }
            }
            lists.add(arrayList);
            arrayList=new ArrayList<>();
            i++;
        }
     return lists;
    }