龙空技术网

LeetCode笔记|111:二叉树的最小深度

可爱小男孩76 77

前言:

现在看官们对“二叉树深度计算公式”大概比较讲究,姐妹们都需要知道一些“二叉树深度计算公式”的相关文章。那么小编同时在网摘上汇集了一些关于“二叉树深度计算公式””的相关文章,希望朋友们能喜欢,各位老铁们快快来学习一下吧!

题目描述

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

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

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

示例

输入:

    3  /    \9     20      /    \   15     7

输出:

2
写在前面

本文答案参考自 LeetCode 官方题解。[敲打]

解法1:深度优先搜索

没什么好说的吧[机智][看]

代码

class Solution {  public int minDepth(TreeNode root) {    if (root == null) {      return 0;    }    if (root.left == null && root.right == null) {      return 1;    }    int min_depth = Integer.MAX_VALUE;    if (root.left != null) {      min_depth = Math.min(minDepth(root.left), min_depth);    }    if (root.right != null) {      min_depth = Math.min(minDepth(root.right), min_depth);    }    return min_depth + 1;  }}作者:LeetCode-Solution链接:来源:力扣(LeetCode)
解法2:广度优先搜索

一层一层地往下找,找到的第一个叶子节点当然就是 距离根节点最近的叶子节点 啦~[耶]

代码

class Solution {  class QueueNode {  TreeNode node;    int depth;    public QueueNode(TreeNode node, int depth) {      this.node = node;      this.depth = depth;    }  }  public int minDepth(TreeNode root) {    if (root == null) {      return 0;    }    Queue<QueueNode> queue = new LinkedList<QueueNode>();    queue.offer(new QueueNode(root, 1));    while (!queue.isEmpty()) {      QueueNode nodeDepth = queue.poll();      TreeNode node = nodeDepth.node;      int depth = nodeDepth.depth;      if (node.left == null && node.right == null) {        return depth;      }      if (node.left != null) {        queue.offer(new QueueNode(node.left, depth + 1));      }      if (node.right != null) {        queue.offer(new QueueNode(node.right, depth + 1));      }    }    return 0;  }}作者:LeetCode-Solution链接:来源:力扣(LeetCode)

标签: #二叉树深度计算公式 #二叉树 宽度