IT工程師數位筆記本

題目描述
從上到下按層打印二叉樹，同一層結點從左至右輸出。每一層輸出一行。

乍一看就是一個BFS，但是因為太久沒刷題都忘記了要使用queue來作為空間存儲容器了。

先參考milolip的代碼，寫出這樣的solution：

class Solution {
public:
    vector<vector<int> > Print(TreeNode* pRoot) {
        vector<vector<int> > res;
        if(pRoot==NULL){
            return res;
        }
        
        queue<TreeNode*> Q;
        Q.push(pRoot);
        Q.push(NULL);
        vector<int> v;
        v.push_back(pRoot->val);
        res.push_back(v);
        v.clear();
        while (!Q.empty()){
            TreeNode* node = Q.front();
            Q.pop();
            if (node != NULL){
                //v.push_back(node->val);
                //cout << node->val << ends;
                if (node->left){
                    Q.push(node->left);
                    v.push_back(node->left->val);
                }
                if (node->right){
                    Q.push(node->right);
                    v.push_back(node->right->val);
                }
            }
            else if (!Q.empty()){
                //cout << "test " << endl;
                Q.push(NULL);
                res.push_back(v);
                v.clear();
                //cout << endl;
            }
        }
        return res;
    }
};

上面的代碼并不太簡潔的樣子。

另一種寫法是從評論區copy來的，又簡潔，又非常直觀清晰。兩層while的嵌套，正好對應到數的層次遍歷以及層內逐點遍歷。而這種雙層嵌套的循環其實并沒有增加復雜度，和原來的復雜度是一樣的。

class Solution_11 {
public:
    vector<vector<int> > Print(TreeNode* pRoot) {
        vector<vector<int> > res;

        if (pRoot == NULL){
            return res;
        }
        
        queue<TreeNode*> q;
        q.push(pRoot);

        while (!q.empty()){
            int lo = 0, hi = q.size();
            vector<int> v;
            while (lo++ < hi){
                TreeNode *t = q.front();
                q.pop();
                v.push_back(t->val);
                if (t->left){
                    q.push(t->left);
                }
                if (t->right){
                    q.push(t->right);
                }
            }
            res.push_back(v);
        }
        return res;
    }
};

測試代碼；

void main_solution_11(){
    Solution_11 s = Solution_11();
    TreeNode* a = new TreeNode(8);
    TreeNode* b1 = new TreeNode(6);
    TreeNode* b2 = new TreeNode(10);
    TreeNode* c1 = new TreeNode(5);
    TreeNode* c2 = new TreeNode(7);
    TreeNode* c3 = new TreeNode(9);
    TreeNode* c4 = new TreeNode(1);

    a->left = b1;
    a->right = b2;

    b1->left = c1;
    b1->right = c2;
    b2->left = c3;
    b2->right = c4;

    vector<vector<int> > q = s.Print(a);
    for (int i = 0; i < q.size(); i++){
        for (int j = 0; j < q[i].size(); j++){
            if (j > 0){
                cout << " ";
            }
            cout << q[i][j];
        }
        cout << endl;
    }
}

int main(){
    main_solution_11();
    return 0;
}