題目網址：https://leetcode.cn/problems/maximum-depth-of-binary-tree/

題意：給一 BT, 求 root-to-leaf 的 path 之最大長度(tree 的最大深度)。

  • 最大長度：path 上的 node 數

Solution 1：

想法：利用 DFS

class Solution {
public:
    int maxDepth(TreeNode* root) {
        if (!root) {
            return 0;
        }
        return 1 + max(maxDepth(root->left), maxDepth(root->right));
    }
};
  • time：$O(n)$ ➔ 遍歷整個 BT
  • space：$O(n)$ ➔ worse case : skew tree, 遞迴深度為 n

Solution 2：

想法：利用 BFS

class Solution {
public:
    int maxDepth(TreeNode* root) {
        if (!root) {
            return 0;
        }

        int res = 0;
        queue<TreeNode*> q;
        q.emplace(root);

        while (!q.empty()) {
            for (int i = q.size(); i > 0; --i) {
                const auto cur = q.front();
                q.pop();

                if (cur->left) {
                    q.emplace(cur->left);
                }

                if (cur->right) {
                    q.emplace(cur->right);
                }
            }

            ++res;
        }

        return res;
    }
};
  • time：$O(n)$ ➔ 遍歷整個 BT
  • space：$O(n)$ ➔ q 中的元素個數不超過 n