算法-求二叉树最小深度-蒲公英云

算法-求二叉树最小深度

基本概念：

二叉树的最小深度：从根节点出发到达叶子节点的经过的最少的节点数。

这里写图片描述

上述这个图，最短路径应该是A-E这一支。

算法思路：
利用深度优先遍历，递归地返回节点路径长度。

递归算法不是很好理解，这里用上图例子说明。

对于算法开始，判断是A否节点是否为空，如果是空则返回0。

此时想知道A节点的到最小深度的叶子节点要根据A节点的两个叶子节点决定，此时，递归开始，run(root->left),run(root->right);

那么，节点B到最小深度的叶子节点长度是根据CD两个节点决定的
，对于有空子节点的节点，深度值=1（自身）+left+right,即lengthC = lenghtD = 1+0+0=1；

对于有两个子节点的节点，例如B，计算深度值=1+min(lengthC,lengthD)=2;
同理对于A的深度值=1+min(lengthB,lengthE)=2；
所求的就是A-E深度=2

具体代码：

int run(TreeNode *root) {
        if(!root)
            return 0;
        int left = run(root->left);
        int right = run(root->right);
        if(left==0 || right==0)
        {
            return 1+left+right;  
        }
        return 1+min(left,right);
    }