人森很精彩，所以要把所有事情都記起來=ˇ=

今天這題算是比較基本的一題吧，是和tree相關的

level order traversal，就是依照leval去做尋訪的動作而已

比如說有一顆這樣的tree

    3
   / \
  9  20
    /  \
   15   7

用level order traversal，就會得到：

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

 

Sol:

其實這算是很基本的，雖然我一開始也不會就是...

主要的概念就是用一個queue去存這個level中的node，然後在讀這些node的值的同時

可以用另一個queue去存這些node的左右node，當作下一輪要讀取的node

如果直接寫成code的話大概是這樣：

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> viRet;
        
        if (root == nullptr)
            return viRet;
        
        queue<TreeNode*> q;
        q.push(root);
        
        while (!q.empty())
        {
            queue<TreeNode*> qTmp;
            vector<int> viTmp;
            
            while(!q.empty())
            {
                TreeNode* node = q.front();
                q.pop();
                
                if (node->left)
                {
                    qTmp.push(node->left);
                }
                
                if (node->right)
                {
                    qTmp.push(node->right);
                }
                
                viTmp.push_back(node->val);
            }
            
            viRet.push_back(viTmp);
            q = qTmp;
        }
        
        return viRet;
    }
};

 

雖然命名簡陋了一點，不過應該不難懂吧

但其實稍微改良一下的話可能會更好：

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> viRet;
        
        if (root == nullptr)
            return viRet;
        
        queue<TreeNode*> q;
        q.push(root);
        
        while (!q.empty())
        {
            int size = q.size();
            vector<int> viTmp;
            
            while (size > 0)
            {
                TreeNode* node = q.front();
                q.pop();
                
                if (node->left)
                {
                    q.push(node->left);
                }
                
                if (node->right)
                {
                    q.push(node->right);
                }
                
                viTmp.push_back(node->val);
                --size;
            }
            
            viRet.push_back(viTmp);
        }
        
        return viRet;
    }
};

 

這邊用size來當作中間迴圈讀取node的次數，如此一來就不必再多使用一個queue了，也避免了最後要複製的步驟

不管是在執行速度或是記憶體消耗都會表現比較好

大概就是這樣啦~ 比較基礎的東西要熟練一點啊~