二叉树最小深度问题

今天药忘吃喽~ 2022-06-17 00:00 215阅读 0赞

【问题描述】：  
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));
    
        } 
    };

![这里写图片描述][SouthEast]

方法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);
    }
    
    }

![这里写图片描述][SouthEast 1]

【总结】：对比了两种方法，都是用了递归和深度优先搜索，但是第二种方法代码比较简洁,运行时间比第一种少了10ms.但其实占用内存都一样，是8816k

[SouthEast]: /images/20220617/5413f615fcf84affbac69c818404a229.png
[SouthEast 1]: /images/20220617/00400c43240d4ed7a6756463b8c086ba.png