LeetCode: 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.

题目大意: 计算给定二叉树的最小深度(根节点到叶节点的最小距离)

解题思路

递归求解，对 minDepth(root) 的计算转换为对其左/右子树的最小深度的计算(min(minDepth(root->left), minDepth(root->right))+1)。当递归过程遇到叶节点时就返回 1，遇到空节点时就返回 0。

AC 代码

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */
class Solution {
public:
    int minDepth(TreeNode* root) {
        // 如果根节点为 nullptr, 则该树的高度为 0
        if(root == nullptr) return 0;

        // 对含有空子树节点的处理
        if(root->left == nullptr) return minDepth(root->right)+1;
        if(root->right == nullptr) return minDepth(root->left)+1;

        return min(minDepth(root->left), minDepth(root->right))+1;
    }
};