博客

层序遍历二叉树

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

For example:

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中。

显然这个题和上面的类似，还是需要借助到队列来完成。

还需要在每次循环每层的时候创建一个一维数组来存储这一层的元素的值，在这次遍历结束后，将该一维数组尾插到最终的二维数组后。

首先还是应该将根节点插入到队列中，取出队列首元素，将该元素的值放在临时的一维数组中，再将该元素的非空左孩子有孩子节点插入到队列中，删除首元素。再循环，直到队列为空，结束循环。得到最后的结果。

需要注意的是：在判断是否该到下一层时，我们需要定义一个临时的队列来暂时存储下一层的节点，为什么？因为有了这个临时的队列，我们可以只判断队列q是否为空，若为空，则表示该层遍历结束，该遍历下一层了。 这时我们再将临时的队列与q交换再继续插入判断即可。

具体实现的代码如下：

 /**
 * Definition for binary tree
 * 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 *head) {
         vector<vector <int> > ret;
        queue<TreeNode*> q;
        queue<TreeNode*> tmp;
        if(head == NULL)
            return ret;
        q.push(head);
        while(!q.empty())
        {
            vector<int> v;
            while(!q.empty())
            {
                TreeNode* front = q.front();
                v.push_back(front->val);
                if(front->left) 
                    tmp.push(front->left);
                if(front->right)
                    tmp.push(front->right);
                q.pop();
            }
            swap(tmp,q);
            ret.push_back(v);
        }
        return ret;
    }
};