Cinte's Leetcode Record
0%

111. Minimum Depth of Binary Tree

Posted on Edited on In Disqus:
Symbols count in article: 2.3k Reading time ≈ 2 mins.

111. Minimum Depth of Binary Tree

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
/**
 * 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) {}
 * };
 */
class Solution {
public:
    int minDepth(TreeNode* root) {
        if(!root) return 0;
        int depth{ INT_MAX };
        int tmp{ 1 };
        backTrack(root, depth, tmp);
        return depth;
    }
private:
    void backTrack(TreeNode* root, int& depth, int& tmp)
    {
        if(!root) return;
        if(!root->left && !root->right)
        {
            depth = min(depth, tmp);
            return;
        }
        ++tmp;
        backTrack(root->left, depth, tmp);
        backTrack(root->right, depth, tmp);
        --tmp;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * 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) {}
 * };
 */
class Solution {
public:
    int minDepth(TreeNode* root) {
        if(!root)
            return 0;
        if(!root->left)
            return minDepth(root->right) + 1; // 针对不是叶子节点的情况，不能因为当前是根而干扰结果
        if(!root->right)
            return minDepth(root->left) + 1; // 针对不是叶子节点的情况，不能因为当前是根而干扰结果
        return min(minDepth(root->left), minDepth(root->right)) + 1; // 如果当前是子树的根节点，那么会导致结果终止于这个根。所以上面2个if是保证在当前节点不是叶子节点情况下继续往下走。
    }
};
BFS
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
/**
 * 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) {}
 * };
 */
class Solution {
public:
    int minDepth(TreeNode* root) {
        if(!root) return 0;
        queue<TreeNode*> q;
        q.push(root);
        int depth{ 0 };
        while(!q.empty())
        {
            ++depth;
            auto sz = q.size();
            for(size_t i = 0; i < sz; ++i)
            {
                auto p = q.front();
                q.pop();
                if(p->left)
                    q.push(p->left);
                if(p->right)
                    q.push(p->right);
                if(!p->left && !p->right)
                    return depth;
            }
        }
        return depth;
    }
};