题目描述
题目链接:111. Minimum Depth of Binary Tree
Given a binary tree, find its minimum depth.
The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.
例子
例子 1
Input: [3,9,20,null,null,15,7]
Output: 2
例子 2
Input: root = [2,null,3,null,4,null,5,null,6]
Output: 5
Note
- A leaf is a node with no children.
解题思路
这道题求二叉树的最浅深度,可以用 DFS 或者 BFS 来求解:
方法一: DFS
通过 DFS 遍历二叉树,并在遇到叶子结点时更新结果即可。为了加快速度,可以在当前深度达到当前最小深度时停止遍历该子树。
代码如下:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36
|
#include <bits/stdc++.h>
class Solution { public: int minDepth(TreeNode* root) { if (!root) return 0; int min_depth = INT_MAX; dfs(root, 0, min_depth); return min_depth; }
private: void dfs(TreeNode* node, int current_depth, int& min_depth) { if (!node || current_depth >= min_depth) { return; } current_depth++; if (!node->left && !node->right) { min_depth = current_depth; }
dfs(node->left, current_depth, min_depth); dfs(node->right, current_depth, min_depth); } };
|
- 时间复杂度: O(n)
- 空间复杂度: O(h) — 遍历深度为最大二叉树最大深度
方法二: BFS
结合 std::queue
和 BFS 按层遍历二叉树,在遇到第一个叶子节点时即可返回当前深度作为结果,代码如下:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
| class Solution { public: int minDepth(TreeNode* root) { queue<TreeNode*>q; if(root==NULL)return 0; q.push(root); int level=0; while(!q.empty()) { int s=q.size(); level++; while(s--) { auto cur=q.front(); q.pop(); if(cur->left)q.push(cur->left); if(cur->right)q.push(cur->right); if(!cur->left&&!cur->right)return level; } } return level; } };
|
GitHub 代码同步地址: 111.MinimumDepthOfBinaryTree.cpp
其他题目:
GitHub: Leetcode-C++-Solution
博客: Leetcode-Solutions