vlambda博客
学习文章列表

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


今天是力扣简单算法第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;};



-End-


喜欢就奖励一个“👍”和“在看”呗~