LeetCode(111):二叉树的最小深度
2023-09-14 09:01:22 时间
Easy!
题目描述:
给定一个二叉树,找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明: 叶子节点是指没有子节点的节点。
示例:
给定二叉树 [3,9,20,null,null,15,7]
,
3 / \ 9 20 / \ 15 7
返回它的最小深度 2.
解题思路:
二叉树的经典问题之最小深度问题就是就最短路径的节点个数,还是用深度优先搜索DFS来完成,万能的递归啊。。。请看代码。
C++解法一:
1 /** 2 * Definition for binary tree 3 * struct TreeNode { 4 * int val; 5 * TreeNode *left; 6 * TreeNode *right; 7 * TreeNode(int x) : val(x), left(NULL), right(NULL) {} 8 * }; 9 */ 10 class Solution { 11 public: 12 int minDepth(TreeNode *root) { 13 if (root == NULL) return 0; 14 if (root->left == NULL && root->right == NULL) return 1; 15 16 if (root->left == NULL) return minDepth(root->right) + 1; 17 else if (root->right == NULL) return minDepth(root->left) + 1; 18 else return 1 + min(minDepth(root->left), minDepth(root->right)); 19 } 20 21 };
相关文章
- Java实现 LeetCode 732 我的日程安排表 III(暴力 || 二叉树)
- Java实现 LeetCode 236 二叉树的最近公共祖先
- Java实现 LeetCode 144 二叉树的前序遍历
- Java实现 LeetCode 124 二叉树中的最大路径和
- Java实现 LeetCode 107 二叉树的层次遍历 II(二)
- Java实现 LeetCode 101 对称二叉树
- Java实现 LeetCode 94 二叉树的中序遍历
- Java实现 LeetCode_0048_RotateImage
- 【LeetCode算法-38】Count and Say
- 【二叉树】LeetCode 543. 二叉树的直径【简单】
- 【二叉树】LeetCode 94. 二叉树的中序遍历【简单】
- LeetCode(114): 二叉树展开为链表
- LeetCode(103): 二叉树的锯齿形层次遍历
- LeetCode-104. 二叉树的最大深度【DFS,BFS】
- ( “树” 之 DFS) 111. 二叉树的最小深度 ——【Leetcode每日一题】
- leetcode 124. 二叉树中的最大路径和
- [LeetCode] 114. 二叉树展开为链表 ☆☆☆(深度遍历)
- 【Leetcode刷题Python】105. 从前序与中序遍历序列构造二叉树
- LeetCode 104. 二叉树的最大深度
- 【LeetCode】958.二叉树的完全性检验