每天进步一点点🤏

二叉树的最小深度

  • ~1.54K 字

二叉树的最小深度

题目

1
2
3
4
5
6
7
8
9
10
11
给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量,包含根节点
说明：叶子节点是指没有子节点的节点。

示例 1：
输入：root = [3,9,20,null,null,15,7]
输出：2

示例 2：
输入：root = [2,null,3,null,4,null,5,null,6]
输出：5

解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
思路:
遍历每一层节点,出现不存在子节点的情况则返回深度

代码:
class TreeNode
{
    public $val = null;
    /**
     * @var TreeNode|null
     */
    public $left = null;
    /**
     * @var TreeNode|null
     */
    public $right = null;

    function __construct($val = 0, $left = null, $right = null)
    {
        $this->val   = $val;
        $this->left  = $left;
        $this->right = $right;
    }
}

/**
 * @param TreeNode $root
 * @return Integer
 */
function minDepth($root) {
    if ($root->val !== null) {
        $queue[] = $root;
        // 如果根节点存在,深度至少为1
        $depth   = 1;
    } else {
        return 0;
    }

    while (1) {
        $queue2 = [];
        // 遍历节点
        foreach ($queue as $node) {
            // 子节点为空, 则当前深度是最小深度, 直接返回
            if ($node->left === null && $node->right === null) {
                return $depth;
            }
            // 子节点不为空, 写入新数组, 在下一次循环中替换当前数组进行遍历
            if ($node->left !== null) {
                $queue2[] = $node->left;
            }
            if ($node->right !== null) {
                $queue2[] = $node->right;
            }
        }
        $queue = $queue2;
        $depth++;
    }

    return $depth;
}