LeetCode 111. Minimum Depth of Binary Tree    原题链接    简单

作者： 作者的头像   yxc ,  2018-05-17 22:12:51 ,  所有人可见 ,  阅读 2691

10


4

题目描述

给定一棵二叉树，找到它的最小深度。

最小深度定义为：从根节点到叶节点的路径长度的最小值。

注意：叶节点定义为没有儿子的节点。

样例

给定二叉树：[3,9,20,null,null,15,7]：

    3
   / \
  9  20
    /  \
   15   7

返回的最小深度是 2。

算法

(递归) $O(n)$

对于每个节点：

  1. 如果没有子节点，说明是叶节点，则返回1；
  2. 如果有子节点，说明是内部结点，则返回子节点的深度的最小值 + 1（加上根节点这层）；

时间复杂度分析：每个节点仅被遍历一次，且遍历时所有操作的复杂度是 $O(1)$，所以总时间复杂度是 $O(n)$。

C++ 代码

/**
 * 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) {
        if (!root) return 0;
        int res = INT_MAX;
        if (root->left) res = min(res, minDepth(root->left) + 1);
        if (root->right) res = min(res, minDepth(root->right) + 1);
        if (res == INT_MAX) res = 1;
        return res;
    }
};

3 评论

用户头像
有心人   2021-07-05 10:39      4    踩      回复 
// 求 二叉树 最小深度，注意陷阱：左右子树中 一个为空，一个不为空的情况
class Solution {
public:
    int minDepth(TreeNode* root) {
        if (!root) return 0; // 递归终止条件
        if (!root->left) return 1 + minDepth(root->right);           // 左
        if (!root->right) return 1 + minDepth(root->left);           // 右
        return min(minDepth(root->left), minDepth(root->right)) + 1; // 中
    }
};
用户头像
小雨   2018-09-11 05:27         踩      回复

我做题目的时候有点没有搞清楚什么是leaf node, leaf node 是没有 children 的node， 所以递归往回传的层数一定要是来自于leaf node 的， 所以感觉这个题的难点在于， 会误把不是leaf node 的结果传上去。 比如左子树存在，右子树不存在。

用户头像
yxc   2018-09-11 09:57         踩      回复

对的，这道题需要先了解叶子结点的定义hh，左右子节点都不存在的点就是叶子结点。