1. 二叉树的最大深度
给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
示例：
给定二叉树 [3,9,20,null,null,15,7]，
3
/ \
9 20
/ \
15 7
返回它的最大深度 3 。
出处：
https://edu.csdn.net/practice/25949981
代码：
import java.util.*; public class maxDepth { public final static int NULL = Integer.MIN_VALUE; //用NULL来表示空节点 public static class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val = x; } } public static class Solution { public int maxDepth(TreeNode root) { if (root == null) { return 0; } int deep = 1; if (root.left == null && root.right == null) { return 1; } int leftDeep = 0; if (root.left != null) { leftDeep = 1 + maxDepth(root.left); } int rightDeep = 0; if (root.right != null) { rightDeep = 1 + maxDepth(root.right); } return deep + leftDeep > rightDeep ? leftDeep : rightDeep; } } public static TreeNode createBinaryTree(Vector<Integer> vec) { if (vec == null || vec.size() == 0) { return null; } Queue<TreeNode> queue = new LinkedList<>(); TreeNode root = new TreeNode(vec.get(0)); queue.offer(root); int i = 1; while (!queue.isEmpty()) { int size = queue.size(); for (int j = 0; j < size; j++) { TreeNode node = queue.poll(); if (i < vec.size() && vec.get(i) != NULL) { node.left = new TreeNode(vec.get(i)); queue.offer(node.left); } i++; if (i < vec.size() && vec.get(i) != NULL) { node.right = new TreeNode(vec.get(i)); queue.offer(node.right); } i++; } } return root; } public static void main(String[] args) { Solution s = new Solution(); Integer[] nums = {3,9,20,NULL,NULL,15,7}; Vector<Integer> vec = new Vector<Integer>(Arrays.asList(nums)); TreeNode root = createBinaryTree(vec); System.out.println(s.maxDepth(root)); } }
输出：
3
2. 二叉树的层序遍历
给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。
示例：
二叉树：[3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回其层序遍历结果：
[
[3],
[9,20],
[15,7]
]
出处：
https://edu.csdn.net/practice/25855085
代码：
import java.util.*; public class levelOrder { public final static int NULL = Integer.MIN_VALUE; //用NULL来表示空节点 public static class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val = x; } } public static class Solution { public List<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>> l = new ArrayList<>(); Queue<TreeNode> q = new LinkedList<TreeNode>(); if (root != null) { q.add(root); } while (!q.isEmpty()) { List<Integer> l2 = new ArrayList<>(); int number = q.size(); while (number > 0) { TreeNode t = q.poll(); l2.add(t.val); if (t.left != null) { q.add(t.left); } if (t.right != null) { q.add(t.right); } number--; } l.add(l2); } return l; } } public static TreeNode createBinaryTree(Vector<Integer> vec) { if (vec == null || vec.size() == 0) { return null; } Queue<TreeNode> queue = new LinkedList<>(); TreeNode root = new TreeNode(vec.get(0)); queue.offer(root); int i = 1; while (!queue.isEmpty()) { int size = queue.size(); for (int j = 0; j < size; j++) { TreeNode node = queue.poll(); if (i < vec.size() && vec.get(i) != NULL) { node.left = new TreeNode(vec.get(i)); queue.offer(node.left); } i++; if (i < vec.size() && vec.get(i) != NULL) { node.right = new TreeNode(vec.get(i)); queue.offer(node.right); } i++; } } return root; } public static void main(String[] args) { Solution s = new Solution(); Integer[] nums = {3,9,20,NULL,NULL,15,7}; Vector<Integer> vec = new Vector<Integer>(Arrays.asList(nums)); TreeNode root = createBinaryTree(vec); System.out.println(s.levelOrder(root)); } }
输出：
[[3], [9, 20], [15, 7]]
3. 最短回文串
给定一个字符串 s，你可以通过在字符串前面添加字符将其转换为回文串。找到并返回可以用这种方式转换的最短回文串。
示例 1：
输入：s = "aacecaaa"
输出："aaacecaaa"
示例 2：
输入：s = "abcd"
输出："dcbabcd"
提示：
0 <= s.length <= 5 * 10^4
s 仅由小写英文字母组成
出处：
https://edu.csdn.net/practice/25949983
代码：
import java.util.*; public class shortestPalindrome { public static class Solution { public static String shortestPalindrome(String s) { StringBuilder r = new StringBuilder(s).reverse(); String str = s + "#" + r; int[] next = next(str); String prefix = r.substring(0, r.length() - next[str.length()]); return prefix + s; } private static int[] next(String P) { int[] next = new int[P.length() + 1]; next[0] = -1; int k = -1; int i = 1; while (i < next.length) { if (k == -1 || P.charAt(k) == P.charAt(i - 1)) { next[i++] = ++k; } else { k = next[k]; } } return next; } } public static void main(String[] args) { Solution s = new Solution(); String str = "aacecaaa"; System.out.println(s.shortestPalindrome(str)); str = "abcd"; System.out.println(s.shortestPalindrome(str)); } }
输出：
aaacecaaa
dcbabcd
