代码随想录 Day16 - 二叉树（三）
作者：jjn0703
- 2023-07-15 江苏
本文字数：1418 字
阅读完需：约 5 分钟
作业题
104. 二叉树的最大深度
递归找到左右子树的最大深度，取其中的较大值+1，即是答案。
package jjn.carl.binary_tree;
import commons.BinaryTreeHelper;import commons.TreeNode;
import java.util.ArrayList;import java.util.List;
/** * @author Jiang Jining * @since 2023-07-14 23:41 */public class LeetCode104 { public int maxDepth(TreeNode root) { if (root == null) { return 0; } int maxLeft = maxDepth(root.left); int maxRight = maxDepth(root.right); return Math.max(maxLeft, maxRight) + 1; } public static void main(String[] args) { List<Integer> input = new ArrayList<>(); input.addAll(List.of(3, 9, 20)); input.add(null); input.add(null); input.addAll(List.of(15, 7)); TreeNode node = BinaryTreeHelper.buildTree(input); int maxDepth = new LeetCode104().maxDepth(node); System.out.println("maxDepth = " + maxDepth); }}
复制代码
111. 二叉树的最小深度
与 104 不一样的是，最小深度要处理仅有左节点或者右节点的情况。
package jjn.carl.binary_tree;
import commons.BinaryTreeHelper;import commons.TreeNode;
import java.util.ArrayList;import java.util.List;
/** * @author Jiang Jining * @since 2023-07-14 23:46 */public class LeetCode111 { public int minDepth(TreeNode root) { if (root == null) { return 0; } if (root.left == null || root.right == null) { return root.left == null ? minDepth(root.right) + 1: minDepth(root.left) + 1; } int minLeft = minDepth(root.left); int minRight = minDepth(root.right); return Math.min(minLeft, minRight) + 1; } public static void main(String[] args) { List<Integer> input = new ArrayList<>(); input.addAll(List.of(3, 9, 20)); input.add(null); input.add(null); input.addAll(List.of(15, 7)); TreeNode node = BinaryTreeHelper.buildTree(input); int minDepth = new LeetCode111().minDepth(node); System.out.println("minDepth = " + minDepth); }}
复制代码
222. 完全二叉树的节点个数
package jjn.carl.binary_tree;
import commons.BinaryTreeHelper;import commons.TreeNode;
import java.util.List;
/** * @author Jiang Jining * @since 2023-07-15 0:00 */public class LeetCode222 { public int countNodes(TreeNode root) { if (root == null) { return 0; } int leftCount = countNodes(root.left); int rightCount = countNodes(root.right); return leftCount + rightCount + 1; } public static void main(String[] args) { List<Integer> list = List.of(1, 2, 3, 4, 5, 6); TreeNode node = BinaryTreeHelper.buildTree(list); int countNodes = new LeetCode222().countNodes(node); System.out.println("countNodes = " + countNodes); }}
复制代码
划线
评论
复制
发布于: 刚刚阅读数: 3
版权声明: 本文为 InfoQ 作者【jjn0703】的原创文章。
原文链接:【http://xie.infoq.cn/article/b1803d2f611ed5024511e213e】。
本文遵守【CC-BY 4.0】协议，转载请保留原文出处及本版权声明。
jjn0703
关注
Java工程师/终身学习者 2018-03-26 加入
USTC硕士/健身健美爱好者/Java工程师.
评论