闯关leetcode——111. Minimum Depth of Binary Tree

题目

地址

https://leetcode.com/problems/minimum-depth-of-binary-tree/description/

内容

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.

Note: A leaf is a node with no children.

Example 1:

Input: root = [3,9,20,null,null,15,7]
Output: 2

Example 2:

Input: root = [2,null,3,null,4,null,5,null,6]
Output: 5

Constraints:

• The number of nodes in the tree is in the range [0, 10⁵].
• -1000 <= Node.val <= 1000

解题

这题要求出一棵树中，从根节点到叶子节点的最短路径长度。这种题目基本都是要进行遍历，但是遍历时有优化空间。比如当某个节点的深度已经超过当前遍历过的最短路径，那么这个节点的子树就不用遍历了。

class Solution {
public:int minDepth(TreeNode* root) {int currentMinDepth = INT_MAX;return minDepthDfs(root, 0, currentMinDepth);}private:int minDepthDfs(TreeNode* root, int depth, int currentMinDepth) {if (root == nullptr) return depth;depth++;if (depth >= currentMinDepth) return depth;if (root->left == nullptr && root->right == nullptr) return depth;if (root->left != nullptr) {currentMinDepth = min(currentMinDepth, minDepthDfs(root->left, depth, currentMinDepth));}if (root->right != nullptr) {currentMinDepth = min(currentMinDepth, minDepthDfs(root->right, depth, currentMinDepth));}return currentMinDepth;}
};

如果我们不考虑这种优化，要走到所有的叶子节点，则可以使用如下的代码。这段代码虽然简洁，但是还是存在优化空间。

    int minDepthDfs(TreeNode* root) {if (root == nullptr) return INT_MAX;if (root->left == nullptr && root->right == nullptr) return 1;return 1 + min(minDepthDfs(root->left), minDepthDfs(root->right));}

代码地址

https://github.com/f304646673/leetcode/tree/main/111-Minimum-Depth%20of-Binary-Tree