vlambda博客
学习文章列表

给定一颗二叉树,找到它的最小深度。

给定一颗二叉树,找到它的最小深度。最小深度是从根节点到最近的叶子节点的最短路径上的节点数量。
大概思路如下:
1、首先判断根节点是否为空,如果为空,则返回0;
2、如果根节点不为空,再去判断左右子节点是否为空,进行递归调用;
3、最后返回leftMin、rightMin中最小的值加1等于二叉树的最小深度;
package com.example.tree;

/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/

public class SolutionMinDepth {

public static int minDepth(TreeNode root) {
if(root == null){
return 0;
}

int leftMin = minDepth(root.left);
int rightMin = minDepth(root.right);

return Math.min(leftMin,rightMin) + 1;
}

public static void main(String[] args) {
TreeNode root = new TreeNode(3);
TreeNode t1 = new TreeNode(9);
TreeNode t2 = new TreeNode(20);
TreeNode t5 = new TreeNode(15);
TreeNode t6 = new TreeNode(7);

root.left = t1;
root.right = t2;
t2.left = t5;
t2.right = t6;

System.out.println(minDepth(root));
}

}
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}


往期内容: