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

传送门

nowcoder
leetcode

题目描述

从上到下按层打印二叉树，同一层结点从左至右输出。每一层输出一行。

C++ 代码 - nowcoder

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

        queue<TreeNode*> q;
        q.push(root);
        while (!q.empty()) {
            int rowLength = q.size();
            vector<int> temp;
            while (rowLength --) {
                TreeNode* node = q.front(); q.pop();
                if (node == nullptr) continue;
                temp.push_back(node->val);
                if (node->left) q.push(node->left);
                if (node->right) q.push(node->right);
            }
            if (temp.size() > 0) res.push_back(temp);
        }
        
        return res;
    }
};

C++ 代码 - leetcode

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

        queue<TreeNode*> q;
        q.push(root);
        // 从上向下一层层遍历
        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);
            }
            res.push_back(level);
        }
        
        return res;
    }
};

题目变形

不分行从上往下打印出二叉树的每个节点，同层节点从左至右打印。

C++ 代码 - nowcoder

class Solution {
public:
    vector<int> PrintFromTopToBottom(TreeNode* root) {
        if (root == nullptr) return vector<int> {};
        
        vector<int> res;
        queue<TreeNode*> q;
        q.push(root);
        while (!q.empty()) {
            int rowLength = q.size();
            while (rowLength --) {
                TreeNode* node = q.front(); q.pop();
                if (node == nullptr) continue;
                res.push_back(node->val);
                if (node->left) q.push(node->left);
                if (node->right) q.push(node->right);
            }
        }
        return res;
    }
};

C++ 代码 - leetcode

class Solution {
public:
    vector<int> decorateRecord(TreeNode* root) {
        if (root == nullptr) return {};

        vector<int> res;
        queue<TreeNode*> q;
        q.push(root);
        while (!q.empty()) {
            int rowLength = q.size();
            while (rowLength --) {
                TreeNode* node = q.front(); q.pop();
                if (node == nullptr) continue;
                res.push_back(node->val);
                if (node->left) q.push(node->left);
                if (node->right) q.push(node->right);
            }
        }
        
        return res;
    }
};