LeetCode 103、二叉树的锯齿形层序遍历

一、题目描述

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

例如： 给定二叉树 [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

返回锯齿形层序遍历如下：

[
  [3],
  [20,9],
  [15,7]
]

二、题目解析

该问题需要用到队列，与之前的二叉树的层次遍历类似，不同点在于在偶数层需要翻转一下。

• 建立一个 queue
• 先把根节点放进去，这时候找根节点的左右两个子节点
• 去掉根节点，此时 queue 里的元素就是下一层的所有节点
• 循环遍历，将结果存到一个一维向量里
• 遍历完之后再把这个一维向量存到二维向量里
• 如果该层为偶数层，则 reverse 翻转一下
• 以此类推，可以完成层序遍历

三、参考代码

1、Java 代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 二叉树的锯齿形层序遍历（ LeetCode 103 ）:https://leetcode-cn.com/problems/binary-tree-zigzag-level-order-traversal/
class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {

        // 设置 res 用来保存输出结果
        List<List<Integer>> res = new LinkedList<List<Integer>>();

        // 边界情况处理
        if(root == null) return res;

        // 设置一个队列，用来存储二叉树中的元素
        Queue<TreeNode> nodeQueue = new LinkedList<TreeNode>();

        // 队列添加二叉树的根节点
        nodeQueue.add(root);

        // 是否从左至右标志位
        boolean isOrderLeft = true;

        // 遍历队列，直到队列为空，说明访问了二叉树中所有的节点
        while (!nodeQueue.isEmpty()) {
            
            // 用来记录 queue 的长度，即每层节点的个数
            int size = nodeQueue.size();

            // 用来保存每一层节点，保存成功后添加到 res 中
            // 由于需要既可以在队头添加元素、有需要可以在队尾添加元素，因此使用双端队列
            // 用双端队列是方便调换方向存储不同层的元素
            Deque<Integer> levelList = new LinkedList<Integer>();

            // 使用 for 循环，将 nodeQueue 中的元素添加的 levelList 中
            // 按标志位存入双端队列，再按固定顺序读取下一层节点值进队列
            for (int i = 0; i < size; ++i) {

                // 从 queue 中取出一个节点，此时，nodeQueue 已经抛出了这个节点         
                TreeNode curNode = nodeQueue.poll();

                // 先从左往右存储，每次存储在 levelList 的队尾，即 addLast
                if (isOrderLeft) {
                    levelList.addLast(curNode.val);
                
                // 再从右往左存储，每次存储在 levelList 的队头，即 addFirst
                } else {
                    levelList.addFirst(curNode.val);
                }

                // 将下一层节点值进入队列，如果有，按照从左到右的顺序
                // 判断当前节点的左子节点是否有值，如果有，则添加到 nodeQueue 中
                if (curNode.left != null) {
                    nodeQueue.add(curNode.left);
                }

                // 判断当前节点的右子节点是否有值，如果有，则添加到 nodeQueue 中    
                if (curNode.right != null) {
                    nodeQueue.add(curNode.right);
                }
            }
            
            // 把存放了每一层元素的数组 levelList 添加到 res 中，注意格式转换，需要转换为数组的形式
            res.add(new LinkedList<Integer>(levelList));

            // 【从左到右】和【从右到左】的顺序来回交替
            isOrderLeft = !isOrderLeft;
        }
        // 返回 res
        return res;
    }
}

**2、**C++ 代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 二叉树的锯齿形层序遍历（ LeetCode 103 ）:https://leetcode-cn.com/problems/binary-tree-zigzag-level-order-traversal/
class Solution {
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {

        // 设置 res 用来保存输出结果
        vector<vector<int>> res;

        // 边界情况处理
        if(root == NULL) return res;

        // 设置一个队列，用来存储二叉树中的元素
        queue<TreeNode*> nodeQueue;

        // 队列添加二叉树的根节点
        nodeQueue.push(root);

        // 是否从左至右标志位
        bool isOrderLeft = true;

        // 遍历队列，直到队列为空，说明访问了二叉树中所有的节点
        while (!nodeQueue.empty()) {

            // 用来记录 queue 的长度，即每层节点的个数
            int size = nodeQueue.size();

            // 用来保存每一层节点，保存成功后添加到 res 中
            // 由于需要既可以在队头添加元素、有需要可以在队尾添加元素，因此使用双端队列
            // 用双端队列是方便调换方向存储不同层的元素
            deque<int> levelList;

            // 使用 for 循环，将 nodeQueue 中的元素添加的 levelList 中
            // 按标志位存入双端队列，再按固定顺序读取下一层节点值进队列
            for (int i = 0; i < size; ++i) {

                // 从 queue 中取出一个节点，此时，nodeQueue 已经抛出了这个节点         
                TreeNode* curNode = nodeQueue.front();
    nodeQueue.pop();

                // 先从左往右存储，每次存储在 levelList 的队尾，即 addLast
                if (isOrderLeft) {
                    levelList.push_back(curNode->val);

                // 再从右往左存储，每次存储在 levelList 的队头，即 addFirst
                } else {
                    levelList.push_front(curNode->val);
                }

                // 将下一层节点值进入队列，如果有，按照从左到右的顺序
                // 判断当前节点的左子节点是否有值，如果有，则添加到 nodeQueue 中
                if (curNode->left != NULL) {
                    nodeQueue.push(curNode->left);
                }

                // 判断当前节点的右子节点是否有值，如果有，则添加到 nodeQueue 中    
                if (curNode->right != NULL) {
                    nodeQueue.push(curNode->right);
                }
            }
   vector<int>v;
   while(!levelList.empty()){
    int element = levelList.front();
    levelList.pop_front();
    v.push_back(element);
   }
            // 把存放了每一层元素的数组 levelList 添加到 res 中，注意格式转换，需要转换为数组的形式
            res.push_back(v);

            // 【从左到右】和【从右到左】的顺序来回交替
            isOrderLeft = !isOrderLeft;
        }
        // 返回 res
        return res;
    }
};

3、Python 代码

# 登录 AlgoMooc 官网获取更多算法图解
# https://www.algomooc.com
# 作者：程序员吴师兄
# 代码有看不懂的地方一定要私聊咨询吴师兄呀
# 二叉树的锯齿形层序遍历（ LeetCode 103 ）:https://leetcode-cn.com/problems/binary-tree-zigzag-level-order-traversal/
class Solution:
    def zigzagLevelOrder(self, root: TreeNode) -> List[List[int]]:

        # 设置 res 用来保存输出结果
        res = [ ]

        # 边界情况处理
        if not root :
           return res

        # 设置一个队列，用来存储二叉树中的元素
        nodeQueue = deque()

        # 队列添加二叉树的根节点
        nodeQueue.append(root)

        # 是否从左至右标志位
        isOrderLeft = True

        # 遍历队列，直到队列为空，说明访问了二叉树中所有的节点
        while nodeQueue :
            
            # 用来记录 queue 的长度，即每层节点的个数
            size = len(nodeQueue)

            # 用来保存每一层节点，保存成功后添加到 res 中
            # 由于需要既可以在队头添加元素、有需要可以在队尾添加元素，因此使用双端队列
            # 用双端队列是方便调换方向存储不同层的元素
            levelList = collections.deque([])

            # 使用 for 循环，将 nodeQueue 中的元素添加的 levelList 中
            # 按标志位存入双端队列，再按固定顺序读取下一层节点值进队列
            for _ in range(size) :

                # 从 queue 中取出一个节点，此时，nodeQueue 已经抛出了这个节点         
                curNode =  nodeQueue.popleft()

                # 先从左往右存储，每次存储在 levelList 的队尾，即 appendLast
                if isOrderLeft :
                    levelList.append(curNode.val)
                
                # 再从右往左存储，每次存储在 levelList 的队头，即 appendFirst
                else :
                   levelList.appendleft(curNode.val)
                

                # 将下一层节点值进入队列，如果有，按照从左到右的顺序
                # 判断当前节点的左子节点是否有值，如果有，则添加到 nodeQueue 中
                if curNode.left :
                    nodeQueue.append(curNode.left)
                

                # 判断当前节点的右子节点是否有值，如果有，则添加到 nodeQueue 中    
                if curNode.right :
                    nodeQueue.append(curNode.right)
          
            
            # 把存放了每一层元素的数组 levelList 添加到 res 中，注意格式转换，需要转换为数组的形式
            res.append(list(levelList))

            # 【从左到右】和【从右到左】的顺序来回交替
            isOrderLeft = not isOrderLeft
        
        # 返回 res
        return res