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

传送门

nowcoder
leetcode

题目描述

给定一个二叉树，返回该二叉树的之字形层序遍历。
（第一层从左向右，下一层从右向左，一直这样交替）

C++ 代码 - nowcoder

/*
    层次遍历，使用一个队列
*/
class Solution {
public:
    vector<vector<int> > Print(TreeNode* pRoot) {
        vector<vector<int>> res;
        if (pRoot == nullptr) return res;

        queue<TreeNode*> q;
        q.push(pRoot);
        bool isLeft = true;
        while (!q.empty()) {
            vector<int> temp;
            int rowLength = q.size();
            while (rowLength --) {
                TreeNode* node = q.front(); q.pop();
                if (node != nullptr) {
                    temp.push_back(node->val);
                    if (node->left) q.push(node->left);
                    if (node->right) q.push(node->right);
                }
            }
            if (!isLeft) {
                reverse(temp.begin(), temp.end());
            }
            isLeft = !isLeft;
            res.push_back(temp);
        }

        return res;
    }
};

C++ 代码 - leetcode

/*
    层次遍历
*/
class Solution {
public:
    vector<vector<int>> decorateRecord(TreeNode* root) {
        vector<vector<int>> res;
        if (!root) return res;

        queue<TreeNode*> q;
        q.push(root);
        // true 从左向右，false 从右向左
        bool isLeft = true;
        // while 循环控制从上向下一层层遍历
        while (!q.empty()) {
            int n = q.size();
            // 记录这一层的节点值
            vector<int> level;
            // 控制每一层从左向右遍历
            while (n --) {
                TreeNode* node = q.front(); q.pop();
                level.push_back(node->val);
                if (node->left) q.push(node->left);
                if (node->right) q.push(node->right); 
            }
            if (!isLeft) reverse(level.begin(), level.end());
            // 交换方向
            isLeft = !isLeft;
            res.push_back(level);
        }

        return res;
    }
};

// 思路同上
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> res;
        if (!root) return res;

        queue<TreeNode*> q;
        q.push(root);
        // 奇数从左向右，偶数从右向左
        int cnt = 0;
        while (!q.empty()) {
            int n = q.size();
            vector<int> level;
            while (n --) {
                TreeNode* node = q.front(); q.pop();
                level.push_back(node->val);
                if (node->left) q.push(node->left);
                if (node->right) q.push(node->right);
            }
            // 交换方向
            if (++ cnt % 2 == 0) {
                reverse(level.begin(), level.end());
            }
            res.push_back(level);
        }

        return res;
    }
};