LeetCode 111. Minimum Depth of Binary Tree [Easy] [C++] 解題筆記

Given a binary tree, find its minimum depth.

The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

Note: A leaf is a node with no children.

Example:

Given binary tree [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

return its minimum depth = 2.

想法:

          這題也是直接 DFS 或是 BFS 搜索即可，要注意的是 leaf node 表示左右皆無子點的 node，因此 [1, 2] 的答案是 2 不是 1，因為 root 1 本身有子點 2 並不算是 leaf node。

完整程式碼:

解法一(recursive):

class Solution {

public:

    int minDepth(TreeNode* root) {

        if (root == nullptr) { return 0; }

        if (root->left == nullptr) { return minDepth(root->right) + 1; }

        if (root->right == nullptr) { return minDepth(root->left) + 1; }

        return min(minDepth(root->left), minDepth(root->right)) + 1;    

    }

};

解法二(iterative):

class Solution {

public:

    int minDepth(TreeNode* root) {

        if (root == NULL) { return 0; }

        int depth = 1;

        queue<pair<TreeNode*, int>> q;

        q.push(make_pair(root, depth));

        while(!q.empty()) {

            auto current = q.front();

            auto current_node = current.first;

            q.pop();

            auto left_child = current_node->left;

            auto right_child = current_node->right;

            

            // leaf node

            if (left_child == NULL && right_child == NULL) {

                depth = current.second;

                break;

            }

            else {

                if (left_child != NULL) 

                    q.push(make_pair(left_child, current.second+1));

                if (right_child != NULL)

                    q.push(make_pair(right_child, current.second+1));

            }

        }

        return depth;

    }

};