闯关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