Leecode 二叉树的锯齿形层序遍历（蛇形打印）

﹏ヽ暗。殇╰゛Y 2023-01-16 06:28 124阅读 0赞

### 文章目录 ###

*  题目
 *  面试题
 *  解法
 *   *  我们想象一下遍历过程
 *  代码
 *  题外（如何构建leecode的二叉树）

# 题目 #

二叉树的锯齿形层序遍历
    
    	给定一个二叉树，返回其节点值的锯齿形层序遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。

# 面试题 #

曾经在腾讯新零售一面就遇到这道题，蛇形打印二叉树。

# 解法 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODMzNjY1OA_size_16_color_FFFFFF_t_70]  
这是一个二叉树，蛇形打印。

## 我们想象一下遍历过程 ##

遍历上一行的时候，下一行的**数字**是跟上一行的从哪到哪的方向一致的，**节点**是相反的！

第一轮：节点1开始遍历，从左往右：节点一样从左往右，**节点**是\[2,3\],**数字**是\[3,2\]，但是在下一轮的时候是从右往左，所以节点在最后需要倒转，即\[3.2\]

第二轮：从右往左遍历节点\[3,2\]  
**节点**是\[7,6,5,4\],数字是\[4,5,6,7\]

为啥要这么设计呢？

1.  分行左右遍历，所以需要调整遍历顺序
2.  需要记录下一行节点，这个节点跟上一行遍历的顺序是相反的

# 代码 #

/** * Definition for a binary tree node. * 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) { 
            if(root==null){ 
                return new ArrayList<>();
            }
            List<List<Integer>> resultList = new ArrayList<>();
            resultList.add(new ArrayList<>(Arrays.asList(root.val)));
            List<TreeNode> nodeList = new ArrayList<>();
            nodeList.add(root);
            int i = 0;
            while (true){ 
                boolean flag;
                if(i%2==0){ 
                    flag = false;
                }else { 
                    flag = true;
                }
                nodeList = getNextNode(resultList,nodeList,flag);
                i+=1;
                if(nodeList.size()==0){ 
                    resultList.remove(resultList.size()-1);
                    return resultList;
                }
            }
        }
    
        public List<TreeNode> getNextNode(List<List<Integer>> resultList ,List<TreeNode> nodeList,boolean leftFlag){ 
            List<TreeNode> nodes = new ArrayList<>();
            List<Integer> list =new ArrayList<>();
            if(leftFlag){ 
                //从左开始遍历
                for(TreeNode node:nodeList){ 
                    if(node.left!=null){ 
                        list.add(node.left.val);
                        nodes.add(node.left);
                    }
                    if(node.right!=null){ 
                        list.add(node.right.val);
                        nodes.add(node.right);
                    }
                }
            }else{ 
                for(TreeNode node:nodeList){ 
                    if(node.right!=null){ 
                        list.add(node.right.val);
                        nodes.add(node.right);
                    }
                    if(node.left!=null){ 
                        list.add(node.left.val);
                        nodes.add(node.left);
                    }
                }
            }
            List<TreeNode> resultNodes = new ArrayList<>();
            for(int i = nodes.size()-1;i>=0;i--){ 
                resultNodes.add(nodes.get(i));
            }
            if(resultList.size()!=0){ 
                resultList.add(list);
            }
            return resultNodes;
        }
    }

# 题外（如何构建leecode的二叉树） #

public static TreeNode arrayToBTree(Integer[] arrs) { 
            if (arrs == null || arrs.length == 0) { 
                return new TreeNode();
            }
    
            List<TreeNode> nodes = new ArrayList<>(arrs.length);
            for (Integer obj : arrs) { 
                TreeNode treeNode = new TreeNode();
                if(treeNode!=null){ 
                    treeNode.val = obj;
                    nodes.add(treeNode);
                }
    
            }
    
            for (int i = 0; i < arrs.length/2 - 1; i++) { 
                TreeNode node = nodes.get(i);
                node.left = nodes.get(i*2 + 1);
                node.right = nodes.get(i*2 + 2);
            }
            // 只有当总节点数是奇数时，最后一个父节点才有右子节点
            int lastPNodeIndex = arrs.length/2 - 1;
            TreeNode lastPNode = nodes.get(lastPNodeIndex);
            lastPNode.left = nodes.get(lastPNodeIndex*2 + 1);
            if (arrs.length%2 != 0) { 
                lastPNode.right = nodes.get(lastPNodeIndex*2 + 2);
            }
    
            return nodes.get(0);
        }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODMzNjY1OA_size_16_color_FFFFFF_t_70]: /images/20221022/71c277a271c14649b50aec489092dde6.png