昨天才說可以期待下週會開始出現一些演算法,馬上就迎來了 543. Diameter of Binary Tree。看來要寫這題之前,勢必先複習一下演算法課程中的一大重點:Tree 以及大名鼎鼎的 Depth-First-Search。再稍微修改一下就可以算出 diameter 囉。

class Solution {
public:
    int getDepth(TreeNode* root, int &d){
        if(!root)
            return 0;

        int l = getDepth(root->left, d);
        int r = getDepth(root->right, d);

        d = max(d, l+r);

        return 1 + max(l, r);
    }

    
    int diameterOfBinaryTree(TreeNode* root) {
        int diameter = 0;
        getDepth(root, diameter);
        return diameter;
    }
};

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *

這個網站採用 Akismet 服務減少垃圾留言。進一步瞭解 Akismet 如何處理網站訪客的留言資料