二叉树最小深度问题-蒲公英云

二叉树最小深度问题

【问题描述】：
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.

给定一个二叉树，求出它的最小深度，最小深度是从根节点到最近的叶子节点的最短路径的节点数。

【思路】：遍历一棵二叉树，从根部看起，查看它是否有左右结点。有五种情况
1.没有根节点，那结果就是0
2.有根节点，没有左右子树，结果为1
3.没有左子树，有右子树。把右子树看成一棵新的树。
4.没有右子树，有左子树。把左子树看成一棵新的树。
5.既有左子树，又有右子树。那就把左右子树分别都看成新的树，最后比较谁的最近叶子的路径短，就取哪边。
因为都把左右子树看成新的树了，所以每一棵树都可以用2-3-4-5来判断找出最近叶子的最短路径。
每一棵树都调用这个判断的方法，所以就是递归
【考察】：树的深度优先遍历结合递归的使用

// c/c++
class Solution {
public:
    int run(TreeNode *root) {
        if(root==NULL)return 0;//树为空
        if(root->left==NULL && root->right==NULL)return 1;//无左右子树
        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));
    } 
};

这里写图片描述

方法2：

// c/c++
//把二叉树的左右子树都分离出来，作为一棵新的树，调用run方法
class Solution{
public:
int run(TreeNode *root){
 if(!root)return 0;
 int l=run(root->left);
 int r=run(root->right);
 if(l==0||r==0){
   return 1+r+l;
}
else return 1+min(l,r);
}
}