[ leetcode ] 111. Minimum Depth of Binary Tree

Binary Tree가 주어졌을 때, root에서 leaf node까지 가장 짧은 경로의 길이를 구하는 문제입니다.

재귀를 이용하여 해당 노드가 NULL이면 0을 반환하고 left, child중 짧은 길이를 반복적으로 반환하면서 해를 구합니다.

이 때 left나 right child중 하나 이상 NULL이면 최소값이 0으로 되므로 조건문으로 큰 값이 포함되도록 해줍니다.

둘 다 NULL이 아닐 때는 둘 중 작은 값, 하나 이상 NULL 이면 1 이거나 값이 있는 것을 반환 하도록 합니다.

(자식 한쪽만 값이 있는 경우 해당 노드는 leaf가 아니므로 leaf의 값을 가져가야 함)

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
#define min(a, b)(a > b ? b : a)

class Solution {
public:
    int minDepth(TreeNode* root) {
    	if (!root) return 0;
        int left = minDepth(root->left);
        int right = minDepth(root->right);
        if (!left || !right) return 1 + left + right;
        return 1 + min(left, right);
    }
};