从零学算法103

103.给你二叉树的根节点 root ，返回其节点值的 锯齿形层序遍历 。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。
示例 1：
输入：root = [3,9,20,null,null,15,7]
输出：[[3],[20,9],[15,7]]
示例 2：
输入：root = [1]
输出：[[1]]
示例 3：
输入：root = []
输出：[]

• 我的原始人解法：层序遍历，每次处理一遍从左到右的和从右到左的遍历，可以直接略过不看

•   public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if(root==null)return res;
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while(!stack.isEmpty()){
            List<Integer> temp = new ArrayList<>();
            Stack<TreeNode> tempStack = new Stack<>();
            // 从左到右遍历节点
            // stack 从左到右存节点，下面的遍历取的时候就相当于从右到左遍历
            for(int i=stack.size();i>0;i--){
                TreeNode node = stack.pop();
                temp.add(node.val);
                if(node.left != null)tempStack.push(node.left);
                if(node.right != null)tempStack.push(node.right);
            }
            stack=tempStack;
            tempStack = new Stack<>();
            res.add(temp);
            temp = new ArrayList<>();
            // 从右到左遍历节点，因为上面是用 stack 从左到右存的
            // stack 从右到左存节点，下一轮的遍历取的时候就相当于从左到右遍历
            for(int i=stack.size();i>0;i--){
                TreeNode node = stack.pop();
                temp.add(node.val);
                if(node.right != null)tempStack.push(node.right);
                if(node.left != null)tempStack.push(node.left);
            }
            stack=tempStack;
            // 如果到这已经遍历完了就不用加了
            if(temp.size()>0)res.add(temp);
        }
        return res;
    }
  

• 他人解法1：层序遍历，用一个变量记录是从左到右还是从右到左存放当前层的值，这样每次遍历都从左到右放节点即可，具体看代码

•   public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if(root==null)return res;
        boolean leftToRight = true;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while(!queue.isEmpty()){
            List<Integer> temp = new ArrayList<>();
            for(int i=queue.size();i>0;i--){
                TreeNode node = queue.poll();
                // 从左到右正常放
                if(leftToRight)temp.add(node.val);
                // 遍历节点的顺序为从左到右，每次把值放首位
                // 这样就相当于从右到左存放了这层的结点的值
                else temp.add(0,node.val);
                if(node.left != null)queue.add(node.left);
                if(node.right != null)queue.add(node.right);
            }
            res.add(temp);
            // 记得下层换顺序了
            leftToRight = !leftToRight;
        }
        return res;
    }
  

• 他人解法2：dfs，其实也可以看做上面 bfs 的递归版本，不过主要难在入参中的当前遍历层 level 可能想不到， level 不仅可以代替 leftToRight 判断存放节点值的顺序，还能根据 level 把节点值存放到对应层的 list，调用递归就相当于节点入队且遍历到了下一层， 具体如下

•   List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        if(root==null)return res;
        dfs(root, 0);
        return res;
    }
    public void dfs(TreeNode root, int level){
        if(root==null)return;
        // 如果当前层还没 list 就先建一个
        if(res.size() <= level){
            List<Integer> levelRes = new ArrayList<>();
            res.add(levelRes);
        }
    	// 第几层的值就存到第几层的 list
        List<Integer> levelRes = res.get(level);
        // 判断存放值的顺序来存放
        if(level%2==0)levelRes.add(root.val);
        else levelRes.add(0, root.val);
    	// 处理下一层
        dfs(root.left, level+1);
        dfs(root.right, level+1);
    }