题目Binary Tree Zigzag Level Order Traversal

Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between).
For example:
Given binary tree [3,9,20,null,null,15,7],
3
/
9 20
/
15 7
return its zigzag level order traversal as:
[
[3],
[20,9],
[15,7]
]

分析

二叉树按照"Z"字遍历,本质还是一个二叉树层次遍历的问题.
只是加入了偶数层结果从左到右存储,奇数行从右到左存储的限制

1,递归

public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        dfs(root,result,0);
        return result;
}
private void dfs(TreeNode root, List<List<Integer>> result,int level){
        if(root == null){
            return;
        }
        
        if(level >= result.size()){
            result.add(new LinkedList<Integer>());
        }
        
        if(level % 2 == 0){
            result.get(level).add(root.val);
        }else{
            result.get(level).add(0,root.val);
        }
        dfs(root.left,result,level+1);
        dfs(root.right,result,level+1);
    }

2,非递归

public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        if(root == null){
            return result;
        }
        List<TreeNode> curLevelNodes = new ArrayList<TreeNode>();
        curLevelNodes.add(root);
        int level = 0;
        while(!curLevelNodes.isEmpty()){
            List<Integer> levelResult = new LinkedList<Integer>();
            List<TreeNode> nextLevelNodes = new ArrayList<TreeNode>();
            for(TreeNode node : curLevelNodes){
                if(level % 2 == 0){
                    levelResult.add(node.val);
                }else{
                    levelResult.add(0,node.val);
                }
                
                if(node.left != null){
                    nextLevelNodes.add(node.left);
                }
                if(node.right != null){
                    nextLevelNodes.add(node.right);
                }
            }
            level++;
            result.add(levelResult);
            curLevelNodes = nextLevelNodes;
        }
        
        return result;
    }