【LeetCode】111. Minimum Depth of Binary Tree解法及注释，Java，C++,DFS

比眉伴天荒 2022-08-21 13:45 8阅读 0赞

### 111. Minimum Depth of Binary Tree   Total Accepted: 104964 Total Submissions: 342426 Difficulty: Easy  ###

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.

【分析】

给定一个二叉树，要求其最小深度，这和**[【LeetCode】104求最大深度的方法][LeetCode_104]**并没有本质的不同，在104题中我提供了一种DFS的方法，但就此题并不能直接套用，毕竟思想有差异：1.初始条件差异，我们将最小深度的初始值设为INT\_MAX（Java中为Integer.MAX\_VALUE）;2.深度值更新条件差异，只有到达叶子结点才更新。此外，我在网上看到一个十分简洁的算法，采用的是递归的思想，这里我直接给出了。

【DFS版】

class Solution {
    public:
        int minDepth(TreeNode* root) 
        {
           if(root==NULL)return 0;
           
           int minDepth=INT_MAX;
           DFS(root,0,minDepth);
           return minDepth;
        }
        
        void DFS(TreeNode* root,int depth,int &minDepth)
        {
            if(root==NULL)return;
            if(root->left==NULL&&root->right==NULL)
            {
                if(depth+1<minDepth)minDepth=depth+1;
            }
            else
            {
                DFS(root->left,depth+1,minDepth);
                DFS(root->right,depth+1,minDepth);
            }
        }
        
    };

【C++版】

/**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    class Solution {
    public:
        int minDepth(TreeNode* root) 
        {
           
            if (root==NULL)return 0;
            int LDepth=minDepth(root->left);
            int RDepth=minDepth(root->right);
            
            if(LDepth==0&&RDepth==0)
            return 1;
            if(LDepth==0)
            LDepth=INT_MAX;
            if(RDepth==0)
            RDepth=INT_MAX;
            
            return min(LDepth,RDepth)+1;
        }
        
    };

【Java版】

###    `/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public int minDepth(TreeNode root) { if(root==null)return 0; if(root.left==null&&root.right==null)return 1; int LDepth=minDepth(root.left); int RDepth=minDepth(root.right); if(LDepth==0) LDepth=Integer.MAX_VALUE; if(RDepth==0) RDepth=Integer.MAX_VALUE; return Math.min(LDepth,RDepth)+1; } }`      ###

[LeetCode_104]: http://blog.csdn.net/jin_kwok/article/details/51163574