Binary Tree Level Order Traversal 二叉树层次遍历（深搜，vector）-白红宇

Binary Tree Level Order Traversal 二叉树层次遍历（深搜，vector）

阅读量：4109 次

发布时间：2019-05-25

本文共 600 字，大约阅读时间需要 2 分钟。

题目：

解答：

这题虽然是要求层次遍历输出每一层的节点，但是也可以通过深度优先搜索完成。

利用vector<vector<int> > res记录结果, 那么res[i]就代表第i层的节点列表。

遍历二叉树时，记录二叉树的深度，将该节点插入到对应深度的列表中，如果对应深度的列表不存在，则先在res中插入一个列表。

代码：

class Solution { public:	 vector
   
    
      > levelOrder(TreeNode *root) {		 vector
     
      
        > res;		 DFS(root, res, 0);		 return res;	 }	 void DFS(TreeNode *root, vector
       
        
          > &res, int deep) { if (root == NULL) return; if (res.size() < deep+1) { vector
         
           temp; res.push_back(temp); } res[deep].push_back(root->val); DFS(root->left, res, deep + 1); DFS(root->right, res, deep + 1); } };