Minimum Depth of Binary Tree (Easy)

Description

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.

Analysis

求树的最小深度。跟最大深度大同小异。dfs遍历一下

My Solution

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
26
27
28
29
30
31
//C++
/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
    int ans = INT_MAX;
    void dfs(TreeNode *root,int depth){
        if(root->left==NULL&&root->right==NULL){
            if(depth<ans)
                ans = depth;
            return;
        }
        if(root->left)
            dfs(root->left,depth+1);
        if(root->right)
            dfs(root->right,depth+1);
    }
public:
    int minDepth(TreeNode *root) {
        if(root==NULL)
            return 0;
        dfs(root,1);
        return ans;
    }
};