103. Binary Tree Zigzag Level Order Traversal #

题目 #

给定二叉树的根节点 root，返回其节点值的 锯齿形层序遍历。

即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行。

思路 #

双栈

代码 #

双栈 #

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> ans = new LinkedList<>();
        if (root == null) return ans;
        
        Stack<TreeNode> leftStack = new Stack<>();
        Stack<TreeNode> rightStack = new Stack<>();
        
        leftStack.push(root);
        while (leftStack.size() != 0 || rightStack.size() != 0) {
            ans.add(new LinkedList<>());
            if (leftStack.size() != 0) {
                while (leftStack.size() != 0) {
                    TreeNode node = leftStack.pop();
                    ans.get(ans.size() - 1).add(node.val);
                    
                    if (node.left != null) rightStack.push(node.left);
                    if (node.right != null) rightStack.push(node.right);
                }
            }
            else {
                while (rightStack.size() != 0) {
                    TreeNode node = rightStack.pop();
                    ans.get(ans.size() - 1).add(node.val);
                    
                    if (node.right != null) leftStack.push(node.right);
                    if (node.left != null) leftStack.push(node.left);
                }
            }
        }
        
        return ans;
    }
}