安徽省和住房建设厅网站,网易企业邮箱官网登录入口,网站制作动态转静态怎么做,怎么做淘宝客优惠劵网站给我们一个二叉树#xff0c;我们应该如何来求二叉树的最小深度呢#xff1f; 二叉树的最小深度指的是叶子结点到所处的位置最小的#xff0c;这就是二叉树的最小深度#xff0c;也就是说我们要找的是离根结点最近的叶子结点。如果我们从根结点向下出发寻找叶子节点#x…给我们一个二叉树我们应该如何来求二叉树的最小深度呢 二叉树的最小深度指的是叶子结点到所处的位置最小的这就是二叉树的最小深度也就是说我们要找的是离根结点最近的叶子结点。如果我们从根结点向下出发寻找叶子节点一层一层的去找叶子结点最先找到的叶子结点所处于的深度就是二叉树的最小深度而叶子结点的标志就是两个指针域都为NULL。所以我们只需要去寻找最先出现的二叉树的两个指针域都为NULL的结点。 但是从上往下去寻找的话分叉是很多的这不方便我们的查找因为分叉越多的话你先选择遍历哪一条分叉呢你怎么知道所选的这一条分叉上的叶子结点离根结点最近呢如果你所选的这一条分叉上找的叶子结点不是离根结点最近的那么你该怎么选择下一个路径呢这些都是我们要考虑的问题就算我们按照从左到右的顺序依次遍历每一条路径去计算路径的长度我们是不是需要建立一个数组来储存每一个叶子结点到根结点的路径长度然后再从中挑选最小的。这是很麻烦的。 但是我们换一个思路从下往上去计算叶子结点到根结点的路径长度因为按照递归递归终止条件一旦达成函数就会逐层返回在二叉树上的表现就是从叶子结点逐层向上。按照下面图示的方法去计算最小深度你看看是不是更为简单叶子结点的深度为1可以看左只有根结点的一颗子树 相信你看了图示之后大概就明白了这就是一个不断地从结点的两个子树中以较矮的子树作为长度然后不断向上知道到达根结点的过程这一过程可以在递归中自动实现。接下来我们来分析递归的终止条件一旦访问到 r o o t N U L L rootNULL rootNULL说明这一个结点不存在可以看作根结点为空的子树深度看作0返回0即可如果访问的当前结点的左孩子为NULL右孩子也为NULL说明此节点为叶子结点按照上图分析叶子结点是起点返回1当访问到空结点时此节点不存在但是如果其兄弟结点存在的话就必定只能从其兄弟所在的路径继续向上也就是以不为0的路径加1作为当前结点所在路径的最短长度。这样我们就分析路径的变化规则我们可以写出下面的代码
int minDepth(struct TreeNode* root) {if(rootNULL)return 0;if(root-leftNULLroot-rightNULL)return 1;int left minDepth(root-left);int right minDepth(root-right);int depth;if(left!0right!0){depth leftright?right1:left1;}if(left0){depth right1;}if(right 0){depth left 1;}return depth;
}运行结果截图
