leetcode-102.层序遍历二叉树(正序)· BTree

题面

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

层序遍历二叉树，要求从上到下，从左到右，输出结果为二维vector。

样例

Given binary tree [3,9,20,null,null,15,7],
    3

   / \

  9  20

    /  \

   15   7
return its level order traversal as:
[

  [3],

  [9,20],

  [15,7]

]

算法

想法：还记得怎么进行层序遍历吗？结果是一个一维数组。现在的情景是要把每一层用一个单独的vector存起来，仅此而已。那么我们的首要问题就是，怎么解决“一层”的问题。

其实，我们在处理完上一层时，queue中就会只包含有本层的节点指针，那么我们计算queue.size()，然后只处理queue的前queue.size()个元素不就可以了吗？在处理其中每一个元素的时候，判空。非空的话，值压入vector，然后把左孩子和有孩子都再次压入queue，最后queue.pop()。处理完这一层，就把当前vector整个压入结果vector<vector<int>> res 中。

1. 根节点判空，若空，返回空vector<vector<int>> (); 不空，继续

2. 新建queue<TreeNode*> q, 和结果vector<vector<int>> res，根节点压入q中

3. 若q非空，while循环判断

新建vector。计算q元素个数，即为一层节点，逐个判空，若不空，值压入vector。然后把子节点压入q中，然后把它弹出queue。

处理完这层，若vector不空，整个压入res中。

4. 返回 res 结束。

源码

 /**

  * 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) {

         //层序遍历

         if(root == nullptr)

             return vector<vector<int>> ();

         vector<vector<int>> res;

         queue<TreeNode*> q;

         q.push(root);

         while(!q.empty())

         {

             int size = q.size();

             vector<int> tmp;

             while(size--)

             {

                 TreeNode* p = q.front();

                 if(p != nullptr)

                 {

                     tmp.push_back(p->val);

                     q.push(p->left);

                     q.push(p->right);

                 }

                 q.pop();

             }

             if(tmp.size() != )

                 res.push_back(tmp);

         }

         return res;

     }

 };

巴特西

leetcode-102.层序遍历二叉树(正序)· BTree

最新文章

热门文章