题目

剑指 Offer 32 - III. 从上到下打印二叉树 III

难度中等64

请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。

思路

从上到下打印二叉树 II的思路文章

• 在 2 中，是打印每层的节点。。。而在3中是之字型打印，3中的和2中不同的地方，也就说要对于对于偶数层的节点要进行逆序打印。
• 所以在2中的思路上，对于偶数层节点进行逆序打印即可。

代码

Java

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        List<List<Integer>> res = new ArrayList<>();
        if(root != null) queue.add(root);
        int count = 0;
        while(!queue.isEmpty()) {
            List<Integer> tmp = new ArrayList<>();
            for(int i = queue.size(); i > 0; i--) {
                TreeNode node = queue.poll();
                tmp.add(node.val);
                if(node.left != null) queue.add(node.left);
                if(node.right != null) queue.add(node.right);
            }
            count++;
            if(count % 2 == 0) {
                Collections.reverse(tmp);
            }
            res.add(tmp);
        }
        return res;
    }
}

C++

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> allNode;
        if (root == nullptr) {
            return allNode;
        }
        queue<TreeNode*> que;
        que.push(root);
        int i = 1;
        while(!que.empty()) {
            int num = que.size();
            vector<int> oneNode;
            for (int i = 0; i < num; i++) {
                TreeNode* t = que.front();
                que.pop();
                oneNode.emplace_back(t->val);
                if (t->left != nullptr) {
                    que.push(t->left);
                }
                if (t->right != nullptr) {
                    que.push(t->right);
                }
            }
            if ((i%2) == 0) {
                reverse(oneNode.begin(), oneNode.end());
            }    
            allNode.emplace_back(oneNode);
            i++;
        }

        return allNode;
    }
};

Python

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def levelOrder(self, pRoot):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        if not pRoot: return []
        res = []
        queue = [pRoot]
        j = -1
        while queue:
            j += 1
            n = len(queue)
            temp = []
            for _ in range(n):
                node = queue.pop(0)
                temp.append(node.val)
                if node.left: queue.append(node.left)
                if node.right: queue.append(node.right)
            if j % 2:
                temp.reverse()
            res.append(temp)
        return res

JS

// ac地址：https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-iii-lcof/
// 原文地址：https://xxoo521.com/2020-02-20-level-travel-3/

/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var levelOrder = function(root) {
    if (!root) return [];
    const queue = [root];
    const res = [];
    let level = 0; // 代表当前层数
    while (queue.length) {
        res[level] = []; // 第level层的遍历结果

        let levelNum = queue.length; // 第level层的节点数量
        while (levelNum--) {
            const front = queue.shift();
            res[level].push(front.val);
            if (front.left) queue.push(front.left);
            if (front.right) queue.push(front.right);
        }
        // 行号是偶数时，翻转当前层的遍历结果
        if (level % 2) {
            res[level].reverse();
        }

        level++;
    }
    return res;
};