作业题
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); } }
