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

题面

给定一个二叉树，找出其最小深度。

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

说明: 叶子节点是指没有子节点的节点。

示例:

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

111.二叉树的最小深度1

返回它的最小深度 2。

思路

这道题和求最大深度差别比较大的。

依然是前序后序遍历均可，前序求的是深度，后续求的是高度。

好好审题：最小深度是从根节点到最近叶子节点的最短路径上的节点数量。注意，是叶子节点。

递归写法

后序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int getDepth(TreeNode* node) {
    if (node == NULL) return 0;
    int leftDepth = getDepth(node->left);   // 左
    int rightDepth = getDepth(node->right); // 右
                                            // 中
    // 当一个节点的【左子树为空，右子树不为空】或【左子树不为空，右子树为空】时不是最低点
    if (node->left == NULL && node->right != NULL)
        return 1 + rightDepth;
    else if (node->left != NULL && node->right == NULL)
        return 1 + leftDepth;
    return 1 + min(leftDepth, rightDepth);
}

int minDepth(TreeNode* root) {
    return getDepth(root);
}

前序

（待补充）

迭代写法

（待补充）