二叉树的深度——答案

vlambda
2021-07-17

二叉树的深度——答案

This browser does not support music or audio playback. Please play it in Weixin or another browser.

104. 二叉树的最大深度

难度简单

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

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数

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

示例：

输入：root = [3,9,20,null,null,15,7] 3 / \ 9 20 / \ 15 7输出：3

解答：使用深度优先遍历

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */class Solution {
 public int maxDepth(TreeNode root) { if(root == null){ return 0; }
 int left = maxDepth(root.left); int right = maxDepth(root.right);
 return left > right ? left + 1 : right + 1; }}

111. 二叉树的最小深度

难度简单

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

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

示例：

输入：root = [3,9,20,null,null,15,7] 3 / \ 9 20 / \ 15 7输出：2
输入：root = [2,null,3,null,4,null,5,null,6]    2     \      3       \        4 \          5 \            6输出：5

解答：使用深度优先遍历

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */class Solution { public int minDepth(TreeNode root) { if(root == null){ return 0; }
 int left = minDepth(root.left); int right = minDepth(root.right);
 return left == 0 ? right + 1 : right == 0 ? left + 1 : (left > right) ? right + 1 : left + 1; }}