力扣题目（九）：二叉树的层序遍历

vlambda
2021-03-13

力扣题目（九）：二叉树的层序遍历

二叉树的层序遍历（Leetcode 102 中等）

给你一个二叉树，请你返回其按层序遍历得到的节点值。（即逐层地，从左到右访问所有节点）。

示例：

二叉树：[3,9,20,null,null,15,7],

9 20

/ \

15 7

返回其层序遍历结果：

[

[3],

[9,20],

[15,7]

]

解析：

今天的题目比较简单，主要的目的是讲解一下队列的应用。二叉树的层序遍历时一种典型的广度优先搜索，即每次搜索时，先搜索当前节点的所有附近节点，逐步推进，与层序遍历一致。

所谓队列，即序列中元素满足先进先出的原则的数据结构。由于层序遍历中，我们需要对每一层从左到右进行遍历，而对于每一个子节点，如果他在另一个子节点的左侧，则其母节点与该节点相同或在其母节点左侧，因此层序遍历中节点满足先进先出原则，可以使用队列这种数据结构。

具体的解法是把每一层的节点放进一个队列中，在出队列时，再将其子节点放入下一层的队列中，二叉树的结构和队列的先进先出特性保证了结果的正确性。

  
    
    
  
   
     
     
   class Solution {
   
     
     
   public:
   
     
     
    vector<vector<int>> levelOrder(TreeNode* root) {
   
     
     
    
   
     
     
    //分为本层和下一层的遍历队列
   
     
     
    queue<TreeNode*> this_level;
   
     
     
    queue<TreeNode*> next_level;
   
     
     
   

   
     
     
    //分层存储数据
   
     
     
    vector<vector<int> > ans;
   
     
     
    vector<int> single_level;
   
     
     
   

   
     
     
    //空树单独处理
   
     
     
    if( root == NULL ) return vector<vector<int>>();
   
     
     
   

   
     
     
    //初始化
   
     
     
    this_level.push(root);
   
     
     
    TreeNode* cur_node;
   
     
     
    while( !this_level.empty() ) {
   
     
     
    single_level.clear();
   
     
     
    //将本层节点输出到结果中
   
     
     
    //将本层节点的所有子节点加入下一层队列中
   
     
     
    while( !this_level.empty() ) {
   
     
     
    cur_node = this_level.front();
   
     
     
    single_level.push_back(cur_node->val);
   
     
     
    if( cur_node->left != NULL ) {
   
     
     
    next_level.push(cur_node->left);
   
     
     
    }
   
     
     
    if( cur_node->right != NULL ) {
   
     
     
    next_level.push(cur_node->right);
   
     
     
    }
   
     
     
    this_level.pop();
   
     
     
    }
   
     
     
    ans.push_back(single_level);
   
     
     
    //将次层队列换为本层队列
   
     
     
    while( !next_level.empty() ) {
   
     
     
    this_level.push(next_level.front());
   
     
     
    next_level.pop();
   
     
     
    }
   
     
     
    }
   
     
     
    return ans;
   
     
     
    }
   
     
     
   };

二叉树的层序遍历二（Leetcode 107 中等）

给定一个二叉树，返回其节点值自底向上的层序遍历。（即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）

例如：

给定二叉树 [3,9,20,null,null,15,7],

9 20

/ \

15 7

返回其自底向上的层序遍历为：

[

[15,7],

[9,20],

[3]

]

解析：

解法基本和上一题相同，需要将不同的层进行反序，只需要先将结果存在一个栈中，再从栈中取出即可。 ‍

  
    
    
  
   
     
     
   class Solution {
   
     
     
   public:
   
     
     
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
   
     
     
    
   
     
     
    //分为本层和下一层的遍历队列
   
     
     
    queue<TreeNode*> this_level;
   
     
     
    queue<TreeNode*> next_level;
   
     
     
   

   
     
     
    //分层存储数据
   
     
     
    vector<vector<int> > ans;
   
     
     
    stack<vector<int> > temp_ans;
   
     
     
    vector<int> single_level;
   
     
     
   

   
     
     
    //空树单独处理
   
     
     
    if( root == NULL ) return vector<vector<int>>();
   
     
     
   

   
     
     
    //初始化
   
     
     
    this_level.push(root);
   
     
     
    TreeNode* cur_node;
   
     
     
    while( !this_level.empty() ) {
   
     
     
    single_level.clear();
   
     
     
    //将本层节点输出到结果中
   
     
     
    //将本层节点的所有子节点加入下一层队列中
   
     
     
    while( !this_level.empty() ) {
   
     
     
    cur_node = this_level.front();
   
     
     
    single_level.push_back(cur_node->val);
   
     
     
    if( cur_node->left != NULL ) {
   
     
     
    next_level.push(cur_node->left);
   
     
     
    }
   
     
     
    if( cur_node->right != NULL ) {
   
     
     
    next_level.push(cur_node->right);
   
     
     
    }
   
     
     
    this_level.pop();
   
     
     
    }
   
     
     
    temp_ans.push(single_level);
   
     
     
    //将次层队列换为本层队列
   
     
     
    while( !next_level.empty() ) {
   
     
     
    this_level.push(next_level.front());
   
     
     
    next_level.pop();
   
     
     
    }
   
     
     
    }
   
     
     
    while( !temp_ans.empty() ) {
   
     
     
    ans.push_back(temp_ans.top());
   
     
     
    temp_ans.pop();
   
     
     
    }
   
     
     
    return ans;
   
     
     
    }
   
     
     
   };