寻找二叉树的最小深度

【T1】

英文题目： Given a binary tree, find its mininum. The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

中文题目： 寻找一棵二叉树的最小深度。最小深度是指从根结点到最近的叶子结点（最短路径）的节点数。

寻找一棵二叉树的最小深度。最小深度是指从根结点到最近的叶子结点（最短路径）的节点数。

先来想一下二叉树的状态：

• 先来想想二叉树的两种极其简单的特殊情况：

（1) 若给定的树是空树，我们可直接返回0。

（2）若给定的树只有根结点，没有左右子树，我们则可直接返回1。

• 剩下来就是可以考虑稍微复杂的正常情况：

（1）若是只有右子树，左子树为空，那么我们可以把右子树当成一个新树，带入run()函数，最小深度则是run(右子树)+1。

（2）若是只有左子树，右子树为空，情况与上类似。

（3）若左右子树均有，则是左子树右子树均计算，将最小的值+1作为原树的最小深度。

找来了个图片举个例，最小深度的路径就是1->2：

代码大致如下：（不断的判断情况加迭代）

class Solution {
public: 
    int run(TreeNode *root) { 
        if(root==NULL){  //空树
            return 0;
        }
        else if(root->left==NULL && root->right==NULL){  //无左右子树，只有根
            return 1;
        }else {   //有左右子树
            if(root->left==NULL){
                return run(root->right)+1;
            }else if(root->right==NULL){
                return run(root->left)+1;
            }else {
                 return 1+min(run(root->left),run(root->right)); 
            }
            
        }
       return 0;
    } 
};

           

本来是去同学推荐的九度oj，不料关辽，所以选择在牛客网做了leetcode的题【第一天特意选了基础题？可我还是提交了n次才过???】,小辣鸡终于要开始决定好好使用oj平台体会做题的快乐555，欢迎指正！

–from一个编程小渣渣