首页 > 代码库 > leetcode题解：Tree Level Order Traversal II （二叉树的层序遍历 2）

leetcode题解：Tree Level Order Traversal II （二叉树的层序遍历 2）

2024-07-10 07:17:43   211人阅读

题目：

Given a binary tree, return the bottom-up level order traversal of its nodes‘ values. (ie, from left to right, level by level from leaf to root).

For example:
Given binary tree {3,9,20,#,#,15,7},

    3   /   9  20    /     15   7

 

return its bottom-up level order traversal as:

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

 

confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.

说明：

        1）与层序遍历1相似，只是本题遍历方向不同：从下往上，其他相同

        2) 代码只要加上一行逆序输出的语句即可

实现：

一、 递归实现：

 1 * 2  * Definition for binary tree 3  * struct TreeNode { 4  *     int val; 5  *     TreeNode *left; 6  *     TreeNode *right; 7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {} 8  * }; 9  */10 class Solution {11     public:12     vector<vector<int> > levelOrder(TreeNode *root) {13         vector<vector<int>> result;14         traverse(root,1,result);15        std::reverse(result.begin(),result.end());//比层序遍历1多此一行16         return result;17     }18     void traverse(TreeNode *root,size_t level,vector<vector<int>> &result)19     {20         if(root==nullptr) return;21         if(level>result.size()) result.push_back(vector<int>());22         result[level-1].push_back(root->val);23         traverse(root->left,level+1,result);24         traverse(root->right,level+1,result);25     }26 };

 

二、迭代实现：

 1 /** 2  * Definition for binary tree 3  * struct TreeNode { 4  *     int val; 5  *     TreeNode *left; 6  *     TreeNode *right; 7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {} 8  * }; 9  */10  /*常规层序遍历思想，每层入队结束压入一个空节点，作为标志*/11 class Solution {12 public:13     vector<vector<int> > levelOrder(TreeNode *root) {14         vector<vector<int>> vec_vec_tree;//创建空vector,存放最后返回的遍历二叉树的值15         vector<int> level;//创建空的vector，存放每一层的遍历二叉树的值16         TreeNode *p=root;17         if(p==nullptr) return vec_vec_tree;//如果二叉树空，返回空vector<vector<int>> 18         queue<TreeNode *> queue_tree;//创建一个空队列19         queue_tree.push(p);//root节点入队列20         queue_tree.push(nullptr);//空节点入队列21         while(!queue_tree.empty())//直到队列为空22         {23             p=queue_tree.front();    //头结点取值，并出队列24             queue_tree.pop();25             if(p==nullptr&&!level.empty())//节点为空并且队列不为空26             {27                 queue_tree.push(nullptr);//入队空节点，与下一层隔开28                 vec_vec_tree.push_back(level);//已遍历的层入队29                 level.clear();//清空vecor level30             }31             else if(p!=nullptr)//如果节点不空32             {33             level.push_back(p->val);//遍历34             if(p->left) queue_tree.push(p->left);//若有左右孩子，则入队列35             if(p->right) queue_tree.push(p->right);//注意入队顺序：先左后右36             }37             38         }39         std::reverse(vec_vec_tree.begin(),vec_vec_tree.end());//比层序遍历1多此一行40         return vec_vec_tree;41     }42 };

     b 迭代实现2

 1 /** 2  * Definition for binary tree 3  * struct TreeNode { 4  *     int val; 5  *     TreeNode *left; 6  *     TreeNode *right; 7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {} 8  * }; 9  */10  /*两个队列实现*/11 class Solution {12 public:13     vector<vector<int> > levelOrder(TreeNode *root) {14         vector<vector<int> > result;15         if(root == nullptr) return result;16          queue<TreeNode*> current, next;//两个队列，保存当层（current）和下层（next）节点17         vector<int> level; // 存放每层的节点值18         current.push(root);19         while (!current.empty())//直到二叉树遍历完成20         {21             while (!current.empty())//直到本层二叉树遍历完成22             {23                 TreeNode* node = current.front();//取队首节点，出队列24                 current.pop();25                 level.push_back(node->val);//访问节点值26                 if (node->left != nullptr) next.push(node->left);//若存在左右节点，则压入next队列中27                 if (node->right != nullptr) next.push(node->right);//注意入队顺序为先left后right28             }29             result.push_back(level);//压入总vector30             level.clear();//清vector31             swap(next, current);//next队列和current队列交换32         }33         std::reverse(result.begin(),result.end());//比层序遍历1多此一行34         return result;35         }36     };

 

 


联系
我们