[leetcode_111] Minimum Depth of Binary Tree

Find the minimum depth of a binary tree, calculated level by level. I used search with pruning. BFS might be faster in terms of time but requires extra space.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    int min;
    void MoveTo(TreeNode *node, int steps) {
        if (node->left == NULL && node->right == NULL) {
            if (steps < min) {
                min = steps;
            }
            return;
        }
        if (node->left != NULL && steps + 1 < min) {
            MoveTo(node->left, steps + 1);
        }
        if (node->right != NULL && steps + 1 < min) {
            MoveTo(node->right, steps + 1);
        }
    }
    int minDepth(TreeNode *root) {
        min = 999999999;
        if (root == NULL)
            return 0;
        MoveTo(root, 1);
        return min;
    }
};