104

截至目前為止，我們已經寫了好幾題binary tree的題目了，隱隱約約會開始發現有些程式碼可以重複使用。例如這題要計算樹的最大深度，就會讓我聯想到之前寫level order traversal的時候，會一層層把val都看過一遍，直到某一層的全部節點都是NULL為止。換句話說，只要在過程中記錄現在的深度(到底現在是在第幾層)，最後跑完迴圈的時候，把深度回傳即可。

雖然想像起來就覺得這個演算法不會很快，畢竟不是為了這題量身打造的演算法，可是一樣有滿足功能上的需求(因為至少可以把問題解出來)，實作出來的程式碼會長得像下面這樣:

/**
 * 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:
    int maxDepth(TreeNode* root) {
        int depth=0;
        vector<TreeNode*> level_list, next_level_list;

        if(root == NULL)
            return 0;
        else if(root->left == NULL && root->right == NULL)
            return 1;
        else
            level_list.push_back(root);

        while(level_list.size() != 0)
        {
            next_level_list.clear();
            for(int i=0; i<level_list.size(); i++)
            {
                if(level_list[i]->left != NULL)
                    next_level_list.push_back(level_list[i]->left);
                if(level_list[i]->right != NULL)
                    next_level_list.push_back(level_list[i]->right);
            }
            level_list = next_level_list;
            depth++;
        }

        return depth;
    }
};

果不其然，速度算是滿慢的: