leetcode-jecklee/MinimumDepthOfBinaryTree.cpp at master · rainlee/leetcode-jecklee · GitHub

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
/*
                   _ooOoo_
                  o8888888o
                  88" . "88
                  (| -_- |)
                  O\  =  /O
               ____/`---'\____
             .'  \\|     |//  `.
            /  \\|||  :  |||//  \
           /  _||||| -:- |||||-  \
           |   | \\\  -  /// |   |
           | \_|  ''\---/''  |   |
           \  .-\__  `-`  ___/-. /
         ___`. .'  /--.--\  `. . __
      ."" '<  `.___\_<|>_/___.'  >'"".
     | | :  `- \`.;`\ _ /`;.`/ - ` : | |
     \  \ `-.   \_ __\ /__ _/   .-` /  /
======`-.____`-.___\_____/___.-`____.-'======
                   `=---='
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
         God Bless Me     BUG Free Forever
*/
/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
/***
 * 法1：递归，每次取左右子树小的一个
 * 从底向上
 ***/
/*
class Solution {
public:
    int minDepth(TreeNode *root) {
        if (NULL == root)
            return 0;

        int minl = minDepth(root->left);
        int minr = minDepth(root->right);

        if (minl && minr)
            return min(minl, minr) + 1;
        else
            return minl + minr + 1;  // (0 == minl) || (0 == minr)
    }
};
*/

/***
 * 法2：递归 + 剪枝
 * DFS 记录当前的mindep
 * 从根向叶子遍历，超过mindep则break
 * 自顶向下
 ***/
class Solution {
public:
    int minDepth(TreeNode *root) {
        if (NULL == root)
            return 0;

        mindep = INT_MAX;
        minDep(root, 0);

        return mindep;
    }
private:
    int mindep;

    void minDep(TreeNode *root, int dep)
    {
        if (NULL == root)
            return;

        if (++dep >= mindep)
            return;

        if ((NULL == root->left) && (NULL == root->right))
        {
            mindep = min(mindep, dep);
            return;
        }

        minDep(root->left, dep);
        minDep(root->right, dep);

        return;
    }
};