[leetcode]Binary Tree Level Order Traversal 层级遍历

层序遍历二叉树

原题&翻译

Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).

给出一棵二叉树,返回层序遍历的节点(层序遍历就是从左到右,从上到下)。

比如给出这样的二叉树:[3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

返回的层序遍历应该是这样的:

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

解体思路

解法一,递归做法

这里唯一要注意的是,二维向量需要动态申请空间,不然会出空指针问题。

class Solution {
public:
    vector<vector<int>> result;
    vector<vector<int>> levelOrder(TreeNode* root) {
        levelTree(root, 0);
        return result;
    }
private:
    void levelTree(TreeNode* root, int levels) {
        if (!root) return;
        if (result.size() == levels) {
            result.push_back(vector<int>());
        }
        result[levels].push_back(root->val);
        levelTree(root->left, levels +1 );
        levelTree(root->right, levels + 1);
    }
};

解法二,队列

yinanxu 的做法,拷贝下来了。具体思路就是存储第一层数据的时候,保存第一层的所有左右孩子到队列中,并记录此时队的长度,保存下一层的时候,队长(chang)范围内遍历这个队列,每遍历一个都将其左右孩子入队,如此往复。

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> result;
        if (!root) return result;
        queue<TreeNode*> q;
        q.push(root);
        int len;
        TreeNode* cur;
        while (!q.empty()) {
            len = q.size();
            vector<int> level;
            for (int i = 0; i < len; ++i) {
                cur = q.front();
                q.pop();
                level.emplace_back(cur->val);
                if (cur->left) q.push(cur->left);
                if (cur->right) q.push(cur->right);
            }
            result.emplace_back(level);
        }
        return result;
    }
};