网站仿造,wordpress重装后404,淘宝网站用什么语言做的,珠海建站网站模板力扣日记#xff1a;【二叉树篇】二叉树的最小深度 日期#xff1a;2023.11.28 参考#xff1a;代码随想录、力扣 111. 二叉树的最小深度
题目描述 难度#xff1a;简单 给定一个二叉树#xff0c;找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点…力扣日记【二叉树篇】二叉树的最小深度 日期2023.11.28 参考代码随想录、力扣 111. 二叉树的最小深度
题目描述 难度简单 给定一个二叉树找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明叶子节点是指没有子节点的节点。
示例 1 输入root [3,9,20,null,null,15,7] 输出2 示例 2 输入root [2,null,3,null,4,null,5,null,6] 输出5 提示
树中节点数的范围在 [0, 10^5] 内-1000 Node.val 1000
题解
递归cpp ver
使用后序遍历记得排除非叶子节点的情况
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
#define SOLUTION 2
class Solution {
public:
#if SOLUTION 1// 1. 递归的参数以及返回值int getDepth(TreeNode* node) {// 2. 终止条件if (node nullptr) return INT_MAX; // 排除不是叶子节点if (node-left nullptr node-right nullptr) return 1; // 当前节点为叶子节点, 返回1(而不是0)// 3. 处理逻辑int leftDepth getDepth(node-left); // 左int rightDepth getDepth(node-right); // 右int depth 1 min(leftDepth, rightDepth); // 中 return depth;}int minDepth(TreeNode* root) {if (root nullptr) return 0;return getDepth(root);}
#elif SOLUTION 2// 1. 递归参数与返回值(输入为当前节点返回值为当前节点的高度)int getDepth(TreeNode* node) {// 2. 终止条件if (node nullptr) return 0;// 3. 处理逻辑// 左int leftDepth getDepth(node-left);// 右int rightDepth getDepth(node-right);// 中// 注意最小深度是根节点到距离最近的叶子节点的节点数因此要排除非叶子节点的情况if (node-left nullptr node-right ! nullptr) {// 当左节点为空而右节点不为空说明左节点不是叶子节点说明最小深度是 1 右子树的深度return 1 rightDepth;}if (node-right nullptr node-left ! nullptr) {// 同理return 1 leftDepth;}// 都不为空则返回两者最小return 1 min(leftDepth, rightDepth);}int minDepth(TreeNode* root) {return getDepth(root);}
#endif
};迭代go ver
使用层序遍历
/*** Definition for a binary tree node.* type TreeNode struct {* Val int* Left *TreeNode* Right *TreeNode* }*/
func minDepth(root *TreeNode) int {queue : list.New()if root ! nil {queue.PushBack(root)}curDepth : 0for queue.Len() 0 {// 记录当前队列长度size : queue.Len()curDepth 1 // 记录当前深度for size 0 { // 处理当前层// 弹出并写入结果front : queue.Front()node : queue.Remove(front).(*TreeNode) // 存进list之后类型会变为*list.Element要转换为*TreeNode// 如果没有左右节点、说明到达了叶子节点当前深度即为最小深度if node.Left nil node.Right nil {return curDepth}if node.Left ! nil {queue.PushBack(node.Left)}if node.Right ! nil {queue.PushBack(node.Right)}size - 1}}return curDepth
}复杂度
时间复杂度 空间复杂度
思路总结
注意最小深度是根节点到距离最近的叶子节点的节点数因此要排除非叶子节点的情况
