二叉树最小深度
参考链接:https://www.nowcoder.com/questionTerminal/e08819cfdeb34985a8de9c4e6562e724?f=discussion
题目描述
求给定二叉树的最小深度。最小深度是指树的根结点到最近叶子结点的最短路径上结点的数量。
基本思路
- 递归思路:
递归,若为空树返回0;
若左子树为空,则返回右子树的最小深度+1;(加1是因为要加上根这一层,下同)
若右子树为空,则返回左子树的最小深度+1;
若左右子树均不为空,则取左、右子树最小深度的较小值,+1;
- 非递规思路:
利用队列采用层序遍历,一旦找到一个叶节点,它肯定是最短的。
代码如下
//递归实现 int DepTreeMinPath(TreeNode *root) { if(root == NULL){ return 0; } if(root->left == NULL){ //如果左子树为空,则返回右子树的最小深度+1 return DepTreeMinPath(root->right) + 1; } else if(root->right == NULL){ //如果右子树为空,则返回左子树的最小深度+1 return DepTreeMinPath(root->left) + 1; } //左右子树都不为空,则取较小值 int LeftHeight = DepTreeMinPath(root->left); int RightHeight = DepTreeMinPath(root->right); return LeftHeight > RightHeight ? (RightHeight + 1) : (LeftHeight + 1); }