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

我会带着你远行 2021-12-19 02:11 160阅读 0赞

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

**题源**：leetcode（[https://leetcode-cn.com/problems/binary-tree-level-order-traversal-ii/）][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; 
         }
     };

[https_leetcode-cn.com_problems_binary-tree-level-order-traversal-ii]: https://leetcode-cn.com/problems/binary-tree-level-order-traversal-ii/%EF%BC%89