从零开始算法之路 ----二叉树的层次遍历 II

前言:小白入门题解，算法大佬可以直接跳过此博客（大佬轻喷哈）

题源：leetcode（https://leetcode-cn.com/problems/binary-tree-level-order-traversal-ii/）

题目描述：

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

解决方案一：递归（利用前序遍历）

思路:

  利用前序遍历从上倒下把节点值存储在一个二重 vector中，返回的时候（或者说输出的时候把容器倒过来，变成题目要求：从下到上），详情看代码。

代码：

/**
 * 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> > levelOrderBottom(TreeNode *root) {	//定义一个二双重vector数	//定义一个二双重vector数组装二叉树节点值 
	vector<vector<int> > binTree;
    //定义一个函数来进行操作 
	levelOrder(root, 0, binTree);
	          c.rbegin() 返回一个逆序迭代器，它指向容器c的最后一个元素
    		  c.rend() 返回一个逆序迭代器，它指向容器c的第一个元素前面的位置
	return vector<vector<int> > (binTree.rbegin(), binTree.rend()); 
     }
    
   //利用前序遍历 
void levelOrder(TreeNode *root, int level, vector<vector<int> > &binTree ){
	//如果树为空结束
	if(!root) return;
	//如果树不为空，开辟一个空间存节点 
	if(level == binTree.size())
		binTree.push_back({}); 
	
	binTree[level].push_back(root->val);
	//如果子树不为空则继续往下执行 
	if(root->left) levelOrder( root->left, level + 1, binTree );
	if(root->right) levelOrder( root->right, level + 1, binTree );
	
}
 };
           

解决方案二：非递归（利用容器 vector 和队列）

思路:

  从上到下遍历存储节点，存储方式稍有不同，类似于栈（先存储的在下面，后存储的在上面，这样就达到了题目要求：返回其自底向上的层次遍历）

代码：

/**
 * 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> > levelOrderBottom(TreeNode *root) {
		// 新建一个双层容器装树的节点值
		vector<vector<int> > res;
		// 如果根节点为空，返回 res
		if( root == NULL) return res;
		// 申明一个 TreeNode* 类型的队列存储 树节点
		queue<TreeNode*> q;
		// 根节点进队列
		q.push(root);
		//队列不为空
		while(!q.empty()){
			// 申明一个单层容器装树每一层节点值
			vector<int> oneLevel;
			// 获取队列大小
			int size = q.size();
			for(int i =0; i < size; i++){
				// 获取队列当前头节点值
				TreeNode *node = q.front();
				// 取得当前头节点值 之后该节点出队列
				q.pop();
				// 把获取到节点对应值存入容器
				oneLevel.push_back(node->val);
				// 如果左右子树不为空，则进队列
				if(node->left) q.push(node->left);
				if(node->right) q.push(node->right);
			} 
			// 每一次都存进容器 res 起始处，这样就达到了题目要求：返回其自底向上的层次遍历
			res.insert(res.begin(),oneLevel);
		}
		return res; 
     }
 };