【算法】二叉树的最小深度

vlambda
2022-04-26

【算法】二叉树的最小深度

今天是力扣简单算法第10题，往期链接如下：

题目来源

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/minimum-depth-of-binary-tree/

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

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

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

分析题目

知识点如下

二叉树的最小高度

先遍历左子树，找出左子树的最小深度，再遍历右子树，找出右子树的最小深度，最终再根节点取左子树和右子树深度最小的那个，加上根节点的高度 1，即 min(leftMindepth, rightMindepth) + 1 为当前二叉树的最小深度。

解答题目

综上分析：

如果左子树为空，右子树不为空，最小深度 = 右子树的深度 + 1。

如果右子树为空，左子树不为空，最小深度 = 左子树的深度 + 1。

如果左右子树都不为空，返回左右子树深度最小值 + 1 。

/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } *//** * @param {TreeNode} root * @return {number} */var minDepth = function(root) { if(!root) return 0 if (root.left === null) return minDepth(root.right) + 1 if (root.right === null) return minDepth(root.left) + 1 return Math.min(minDepth(root.left), minDepth(root.right)) + 1;};