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

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

  • 最小長度: path 上的 node 數

注意：若今給一 skew tree, 則 min_depth = n

Solution 1：

想法：利用 BFS

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

        int depth = 1;
        queue<TreeNode*> q;
        q.push(root);

        while (!q.empty()) {
            const int size = q.size();

            for (int i = 0; i < size; ++i) {
                const auto node = q.front();
                q.pop();

                if (node->left) {
                    q.push(node->left);
                }

                if (node->right) {
                    q.push(node->right);
                }

                if (!node->left && !node->right) {
                    return depth;
                }
            }

            ++depth;
        }

        return depth;
    }
};
  • time：$O(n)$ ➔ skew tree, 需遍歷所有 node
  • space：$O(n)$ ➔ skew tree, stack 長度為 n

Solution 2：

想法：利用 DFS

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

        if (root->left && !root->right) {
            return 1 + minDepth(root->left);
        }

        if (!root->left && root->right) {
            return 1 + minDepth(root->right);
        }

        return 1 + min(minDepth(root->left), minDepth(root->right));
    }
};
  • time：$O(n)$ ➔ skew tree, 需遍歷所有 node
  • space：$O(n)$ ➔ skew tree, stack 長度為 n