二叉树的最小深度

WindrunnerMax

发布于 2020-08-27 12:19:02

3390

发布于 2020-08-27 12:19:02

文章被收录于专栏：Czy‘s BlogCzy‘s Blog

二叉树的最小深度

给定一个二叉树，找出其最小深度。最小深度是从根节点到最近叶子节点的最短路径上的节点数量。说明: 叶子节点是指没有子节点的节点。

示例

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

题解

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

思路

使用深度优先搜索的方法，遍历整棵树对比最小高度的子树并记录，返回最小高度子树的高度，对于每一个非叶子节点，只需要分别计算其左右子树的最小叶子节点深度即可，注意题目中定义最小深度是从根节点到最近叶子节点的最短路径上的节点数量，且叶子节点是指没有子节点的节点，所以有两个节点的二叉树的最小深度是2。首先如果节点没有定义，那么就认为其高度为0并返回0，对于题目中的要求最小深度是从根节点到最近叶子节点的最短路径上的节点数量，所以在左子树不存在右子树存在的情况下，返回右子树的最小深度+1，如果在右子树不存在左子树存在的情况下，返回左子树的最小深度+1，然后取得左子树的最小深度与右子树的最小深度，比较大小，返回较小子树深度+1。