從零開始算法之路 ----二叉樹的層次周遊 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; 
     }
 };