每天一道leetcode-103二叉树的锯齿形层次遍历

/**
 * 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) {
        TreeNode pRoot = root;
        Stack<TreeNode> stack1 = new Stack<>();
        Stack<TreeNode> stack2 = new Stack<>();
        ArrayList<Integer> tempResult = new ArrayList<>();
        List<List<Integer>>  resultList = new ArrayList<>();
        if(pRoot == null)
            return resultList;
        int layerCount = 1;
        stack1.push(pRoot);
        while(!stack1.isEmpty() || !stack2.isEmpty())
        {

            while(!stack1.isEmpty())
            {
                TreeNode tempNode = stack1.pop();
                if(tempNode.left != null)
                {
                    stack2.push(tempNode.left);//stack2中按照先左后右的方式入栈，
                }//那么下一层就是按照先右后左出栈，完成之字形。
                if(tempNode.right != null)
                    stack2.push(tempNode.right);
                tempResult.add(tempNode.val);
                if(stack1.isEmpty())
                {//stack1为空，说明stack1中存的这些节点打印完了，所以要把这一层的节点内容存入结果中
                    resultList.add(new ArrayList<Integer>(tempResult));
                    tempResult.clear();
                }
            }
            while(!stack2.isEmpty())
            {//这里大体思路和上面相同，要注意的就是由于上一层已经是逆序打印
                TreeNode tempNode = stack2.pop();//所以这一层必须先右后左入栈，才能确保是顺序打印
                if(tempNode.right != null)
                {
                    stack1.push(tempNode.right);
                }
                if(tempNode.left != null)
                    stack1.push(tempNode.left);
                tempResult.add(tempNode.val);
                if(stack2.isEmpty())
                {
                    resultList.add(new ArrayList<Integer>(tempResult));
                    tempResult.clear();
                }
            }
        }
        return resultList;
    }
}