# geektime-algo **Repository Path**: qiancheung/geektime-algo ## Basic Information - **Project Name**: geektime-algo - **Description**: 极客时间 - 数据结构与算法之美 - **Primary Language**: Java - **License**: Not specified - **Default Branch**: master - **Homepage**: None - **GVP Project**: No ## Statistics - **Stars**: 0 - **Forks**: 5 - **Created**: 2025-04-11 - **Last Updated**: 2025-04-11 ## Categories & Tags **Categories**: Uncategorized **Tags**: None ## README # leetcode ## 最长回文子串（5） https://leetcode.cn/problems/longest-palindromic-substring/ ### 动态规划 #### 思路 一个长度大于 2 的回文串，去掉首尾两个字符后仍然是回文串。例如 abcba 去掉 首尾的 a 后，bcb 仍然是回文串。 我们用 `S[i, j]` 表示，字符串从 i 到 j。例如：字符串是 "babad" 那么，`S[0, 2]` = "bab"; `S[1, 2]` = ab。 用 `S(i)` 表示 字符 i。例如：字符串是 "babad" 那么，`S(0)` = "b"; `S(1)` = "a"。 如果 `S[i, j]` 为回文串，那么 `S[i + 1, j - 1]` 必然也是回文串，并且，`S(i)== S(j)`。 经过以上分析，我们可以得到一个二维数组 `dp[i][j]` 表示，`S[i, j]` 是否为回文串。 又因为如果 `S[i + 1, j - 1]` 是回文串，我们可以通过 `S[i + 1, j - 1]` 推导出 `S[i, j]` 是否为回文串，当 `S(i)== S(j)` 时`S[i, j]` 是回文串。 那么，我们的 dp 数组在推导过程中，需要用到左下角的值。所以，二维数组的递推方向是：从下到上，从左到右 下表 i 为纵坐标，j 为横坐标，T 和 F 表示是否为回文子串 | | b（j0） | a（j1） | b（j2） | a（j3） | d（j4） | | :-----: | :-----: | :-----: | :-----: | :-----: | :-----: | | b（i0） | T | F | T | F | F | | a（i1） | | T | F | T | F | | b（i2） | | | T | F | F | | a（i3） | | | | T | F | | d（i4） | | | | | T | #### 代码 ```java public String longestPalindromeDp(String s) { if (s == null) return null; char[] cs = s.toCharArray(); if (cs.length <= 1) return s; // 最长回文子串的长度 int maxLen = 1; // 最长回文子串的开始索引 int begin = 0; // dp[i][j] 表示 s[i..j] 是否是回文串 // dp[i][j] 是回文串，要求 cs[i] == cs[j] && dp[i + 1][j - 1] 是回文串 boolean[][] dp = new boolean[cs.length][cs.length]; // i 从下到上 for (int i = cs.length - 1; i >= 0; i--) { // j 从左到右 for (int j = i; j < cs.length; j++) { // cs[i, j] 的长度 int len = j - i + 1; // 首尾字符必须相等 && （字符串长度小于等于2 或 里面的字符也是回文子串） dp[i][j] = (cs[i] == cs[j]) && (len <= 2 || dp[i + 1][j - 1]); if (dp[i][j] && len > maxLen) { // 说明 cs[i, j] 是回文子串 maxLen = len; begin = i; } } } return new String(cs, begin, maxLen); } ``` ## 正则表达式匹配（10） https://leetcode.cn/problems/regular-expression-matching/ ### 动态规划 #### 思路 本题最难理解的地方就是 * 号。例如模式串 ab*c 可以匹配 "ac"，也可以匹配 "abc"，还可以匹配 "abbbbbc"。 如果 S(i) 表示，字符串的第 i 个字符；P(j) 表示，模式串的第 j 个字符， 如果 P(j + 1) 为 *，有两种情况需要考虑 - S(i) == P(j) - P(j) 有可能匹配多个字符，S 为 "abbbbbc"，P 为 "ab*c"，i 和 j 都为 1，此时 P(j) 匹配了多个字符 - P(j) 也有可能匹配 0 个字符，S 为 "c"，P 为 "c*c"，i 和 j 都为 0，此时 P(j) 匹配 0 个字符 - S(i) ！= P(j) - P(j) 只能匹配 0 个字符，S 为 "ac"，P 为 "ab*c"，i 和 j 都为 1，此时 P(j) 匹配 0 个字符 现在思路已经清晰了，那匹配 * 号的时候我们要匹配 1 次还是多次呢？这就是动态规划，它的状态是 i 和 j 指针，选择是 P(j) 匹配多少次。 #### 代码 ```java // key: i_j（表示：字符串从第 i 个位置与模式串从第 j 个位置进行匹配）, value: 字符串与模式串是否匹配 private Map map = new HashMap<>(); public boolean isMatch(String s, String p) { return dp(s.toCharArray(), 0, p.toCharArray(), 0); } /** * 字符串从第 i 个位置与模式串从第 j 个位置进行匹配，如果匹配返回 true * @param s 字符串 * @param i 字符串从第几个字符开始与模式串进行匹配 * @param p 模式串 * @param j 模式串从第几个字符开始与字符串进行匹配 * @return */ private boolean dp(char[] s, int i, char[] p, int j) { // 字符串匹配完毕 if (i == s.length) { // 剩余的字符必须是 字符* 的组合才能匹配空串，所以，必须是偶数。不是偶数就没法匹配了 if ((p.length - j) % 2 == 1) return false; // 检查剩余字符是否为 字符* 这种成对出现的组合 for (; j + 1 < p.length; j+=2) { if (p[j + 1] != '*') return false; } } // 模式串匹配完毕 if (j == p.length) { // 判断字符是否也已经匹配完毕 return i == s.length; } String key = i + "_" + j; if (map.containsKey(key)) return map.get(key); boolean res = false; if (s[i] == p[j] || p[j] == '.') { // i 和 j 位置的字符匹配 // j + 1 是 * if (j < p.length - 1 && p[j + 1] == '*') { // 匹配 0 次（既：模式串跳过 j 和 j + 1，从 j + 2 位置继续与 s[i] 匹配） || 匹配多次（既：模式串不动，继续与 s[i + 1] 匹配） res = dp(s, i, p, j + 2) || dp(s, i + 1, p, j); } else { // s 和 p 匹配 1 次 res = dp(s, i + 1, p, j + 1); } } else { // i 和 j 位置的字符不匹配 // j + 1 是 * if (j < p.length -1 && p[j + 1] == '*') { // 匹配 0 次（既：模式串跳过 j 和 j + 1，从 j + 2 位置继续与 s[i] 匹配） res = dp(s, i, p, j + 2); } else { res = false; } } map.put(key, res); return res; } ``` ## 括号生成(22) ### 递归隐式回溯 #### 思路 选择左右括号的规则为 - 选择左括号，左括号的数量 < 左右括号的最大数量 `注：当左括号、右括号的数量一样时，只能选择左括号` - 选择左括号，右括号的数量 < 左括号的数量 #### 代码 ```java public List generateParenthesis(int n) { // 特殊条件判断 List retList = new ArrayList<>(); if (n < 0) return retList; dfs(retList, new char[n << 1], 0, 0, n); return retList; } /** * 根据指定条件生成对应的 括号 * @param list 存放结果 * @param path 存放当前的的选择 * @param l 左括号的数量 * @param r 右括号的数量 * @param max 左右括号的最大值 */ private void dfs(List list, char[] path, int l, int r, int max) { // 当前索引 int pos = l + r; // 终止条件 if (pos == path.length) { list.add(new String(path)); return; } // 选择左括号 // 剩余左括号的数量 > 0 // 注：当左括号、右括号的数量一样时，只能选择左括号 if (l < max) { path[pos] = '('; dfs(list, path, l + 1, r, max); } // 选择右括号 // 右括号的数列 > 0 && 右括号的数量 != 左括号的数量 if (r < l) { path[pos] = ')'; dfs(list, path, l, r + 1, max); } } ``` ### 按括号序列的长度递归 #### 思路 任何一个括号序列都一定是由 ‘(’ 开头，并且第一个 ‘(’ 一定有一个唯一与之对应的 ‘)’。这样一来，每一个括号序列可以用 (a)b 来表示，其中 a 与 b 分别是一个合法的括号序列（可以为空）。 那么，要生成所有长度为 2*n* 的括号序列，我们定义一个函数 *generate*(*n*) 来返回所有可能的括号序列 - 我们需要枚举与第一个 ‘(’ 对应的 ‘)’ 的位置 2*i*+1，i 表示，表达式 a 有多少对合法的括号 - 递归调用 *generate*(*i*) 即可计算 *a* 的所有可能性 - 递归调用 *generate*(*n*−*i*−1) 即可计算 *b* 的所有可能性 `总数量 - a 的数量 - 一对左右括号` - 遍历 *a* 与 *b* 的所有可能性并拼接，即可得到所有长度为 2*n* 的括号序列 #### 代码 ```java private List[] cache = new ArrayList[9]; public List generateParenthesis(int n) { return generate(n); } /** * 生成所有可能的括号序列 * @param n * @return */ public List generate(int n) { if (cache[n] != null) { return cache[n]; } List ans = new ArrayList<>(); if (n == 0) { ans.add(""); } else { // 所有可能的组合为：(a)b // 表达式 a 中有多少对合法的括号的取值范围：[0, n - 1] for (int aNum = 0; aNum < n; ++aNum) { // 当 a 等于 aNum 时，所有可能 for (String a: generate(aNum)) { // 遍历 a 为 aNum 时，b 的所有可能（b 的个数通过 n - aNum - 1 计算） for (String b: generate(n - aNum - 1)) { ans.add("(" + a + ")" + b); } } } } cache[n] = ans; return ans; } ``` ## 最长有效括号(32) https://leetcode.cn/problems/longest-valid-parentheses/description/ ### 动态规划 #### 思路 假设 dp[i] 表示以下标 i 字符结尾的最长有效括号的长度。以 ‘(’ 结尾的子串对应的 *dp* 值必定为 0 从左到右一个一个地遍历字符串求解 dp 值，我们每次都检查最后两个字符，可能有下面两种情况 - `s[i] = ')' && s[i − 1] = '('`，也就是字符串形如 “……()”，我们可以推出：`dp[i] = dp[i − 2] + 2` - `s[i] = ')' && s[i − 1] = ')'`，也就是字符串形如 “……))”，我们可以推出：如果 `s[i − dp[i − 1] − 1] = '('`，那么 `dp[i] = dp[i − 1] + 2 + dp[i − dp[i − 1] − 2]` - `dp[i − 1]` 表示以下标 `i - 1` 字符结尾的最长有效括号的长度，也就是字符串形如 “……(`()()()`)”，红色部分是`dp[i − 1]` - 所以 `s[i − dp[i − 1] − 1]` 表示应该与 `s[i]` 对应的左括号的位置，也就是字符串形如 “……`(`()()())”，红色部分是`s[i − dp[i − 1] − 1]` - 如果这里是左括号，那么，最长有效括号的长度就应该是 dp[i − 1] + 2，再加上它们前面的有效括号长度，也就是字符串形如“……(`(())`(()()())”，红色部分是前面的有效括号长度 #### 代码 ```java public int longestValidParentheses(String s) { int maxLen = 0; int[] dp = new int[s.length()]; for (int i = 1; i < s.length(); i++) { // 只需要判断以 ')' 结尾的字符，因为以 '(' 结尾的字符都是非法字符 dp[i] 一定等于 0 if (s.charAt(i) == ')') { if (s.charAt(i - 1) == '(') { // 情况一 dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2; } else if (i - dp[i - 1] > 0 && s.charAt(i - dp[i - 1] - 1) == '(') { // 情况二 dp[i] = dp[i - 1] + 2 + ((i - dp[i - 1]) >= 2 ? dp[i - dp[i - 1] - 2] : 0); } maxLen = Math.max(maxLen, dp[i]); } } return maxLen; } ``` ### 栈 #### 思路 始终保持栈底元素为当前已经遍历过的元素中「最后一个没有被匹配的右括号的下标」，这样的做法主要是考虑了边界条件的处理，栈里其他元素维护左括号的下标 - 对于遇到的每个 ‘(’ ，我们将它的下标放入栈中 - 对于遇到的每个 ‘)’ ，我们先弹出栈顶元素表示匹配了当前右括号 - 如果栈为空，说明当前的右括号为没有被匹配的右括号，我们将其下标放入栈中来更新我们之前提到的「最后一个没有被匹配的右括号的下标」 - 如果栈不为空，当前右括号的下标减去栈顶元素即为「以该右括号为结尾的最长有效括号的长度」 需要注意的是，如果一开始栈为空，第一个字符为左括号的时候我们会将其放入栈中，这样就不满足提及的「最后一个没有被匹配的右括号的下标」，为了保持统一，我们在一开始的时候往栈中放入一个值为 −1 的元素 #### 代码 ```java public int longestValidParentheses(String s) { int maxLen = 0; Stack stack = new Stack<>(); stack.push(-1); for (int i = 0; i < s.length(); i++) { // 对于遇到的每个 ‘(’ ，我们将它的下标放入栈中 if (s.charAt(i) == '(') { stack.push(i); } else { // 对于遇到的每个 ‘)’ ，我们先弹出栈顶元素表示匹配了当前右括号 stack.pop(); // 如果栈为空，说明当前的右括号为没有被匹配的右括号 if (stack.isEmpty()) { // 我们将其下标放入栈中来更新我们之前提到的「最后一个没有被匹配的右括号的下标」 stack.push(i); } else { // 如果栈不为空，当前右括号的下标减去栈顶元素即为「以该右括号为结尾的最长有效括号的长度」 maxLen = Math.max(maxLen, i - stack.peek()); } } } return maxLen; } ``` ### 不需要额外的空间 #### 思路 l 表示，左括号的数量 r 表示，右括号的数量 从左到右遍历 - 当 l == r 时，我们计算最长子字符串 - 当 r > l 时，为非法字符串，将 l 和 r 置为 0 但是，从左到右遍历无法处理 (() 这种情况 所以，我们在从右向左遍历 - 当 l == r 时，我们计算最长子字符串 - 当 l > r 时，为非法字符串，将 l 和 r 置为 0 #### 代码 ```java public int longestValidParentheses(String s) { // 有效括号最大长度 int maxLen = 0; // 左右括号个数 int l = 0; int r = 0; // 从左向右遍历 for (int i = 0; i < s.length(); i++) { if (s.charAt(i) == '(') { l++; } else { r++; } if (l == r) { maxLen = Math.max(maxLen, 2 * l); } else if (r > l) { l = r = 0; } } // 从右向左遍历 l = r = 0; for (int i = s.length() - 1; i >= 0; i--) { if (s.charAt(i) == '(') { l++; } else { r++; } if (l == r) { maxLen = Math.max(maxLen, 2 * l); } else if (l > r) { l = r = 0; } } return maxLen; } ``` ## 接雨水(42) https://leetcode.cn/problems/trapping-rain-water/description/ ### 动态规划 #### 思路 - 定义 lMax[i] 表示，向左查找索引 [0, i] 的最大高度 - 定义 rMax[i] 表示，向右查找索引 [i, n - 1] 的最大高度 - 位置 i 能接的雨水就是 min(lMax[i], rMax[i]) - height[i] #### 代码 ```java public int trap(int[] height) { int n = height.length; if (n == 0) return 0; // lMax[i] 表示，向左查找索引 [0, i] 的最大高度 int[] lMax = new int[n]; lMax[0] = height[0]; for (int i = 1; i < n; ++i) { lMax[i] = Math.max(lMax[i - 1], height[i]); } // rMax[i] 表示，向右查找索引 [i, n - 1] 的最大高度 int[] rMax = new int[n]; rMax[n - 1] = height[n - 1]; for (int i = n - 2; i >= 0; --i) { rMax[i] = Math.max(rMax[i + 1], height[i]); } // 位置 i 能接的雨水就是 min(lMax[i], rMax[i]) - height[i] // 循环计算总共可以接的雨水 int sum = 0; for (int i = 0; i < n; ++i) { sum += Math.min(lMax[i], rMax[i]) - height[i]; } return sum; } ``` ### 单调栈 #### 思路 栈中存储的是 height 数组的下标 && height[i] 递减。 从左到右遍历数组，遍历到下标 *i* 时，如果栈内至少有两个元素，记栈顶元素为 *top*，*top* 的下面一个元素是 *left* - 如果 `height[i] > height[top]`，则得到一个可以接雨水的区域，该区域的宽度是 `i−left−1`，高度是 `min(height[left], height[i]) − height[top]`，根据宽度和高度即可计算得到该区域能接的雨水 #### 代码 ```java public int trap(int[] height) { int sum = 0; // 栈中存储的是 height 数组的下标 && height[i] 递减 Stack stack = new Stack<>(); int n = height.length; for (int i = 0; i < n; ++i) { while (!stack.isEmpty() && height[i] > height[stack.peek()]) { int top = stack.pop(); // 如果栈中元素少于 2 个直接退出 while 循环 if (stack.isEmpty()) { break; } // 走到这里表示，栈中至少有 2 个元素。有可接雨水的区域 int left = stack.peek(); // 计算可接雨水的宽度 int currWidth = i - left - 1; // height[top] 相当于水位的底线，避免重复计算 int currHeight = Math.min(height[left], height[i]) - height[top]; sum += currWidth * currHeight; } stack.push(i); } return sum; } ``` ## 不同的二叉搜索树 II(95) ```java public List generateTrees(int n) { if (n == 0) return new ArrayList<>(); return generateTrees(1, n); } /** * 返回节点值 [start,end] 的所有符合题意的二叉搜索树 * @param start * @param end * @return */ private List generateTrees(int start, int end) { List all = new ArrayList<>(); // 表示空树 if (start > end) { all.add(null); return all; } // 已 i 为根节点 for (int i = start; i <= end; i++) { List allLeft = generateTrees(start, i - 1); List allRight = generateTrees(i + 1, end); // 选一棵左子树 for(TreeNode left : allLeft) { // 选一棵右子树 for(TreeNode right : allRight) { // 以 i 为根节点构建树 TreeNode cur = new TreeNode(i); cur.left = left; cur.right = right; all.add(cur); } } } return all; } ``` ## 不同的二叉搜索树(96) ```java public int numTrees(int n) { // dp[i] 表示，由 i 个节点组成且节点值从 1 到 i 互不相同的二叉搜索树有多少种？ int[] dp = new int[n + 1]; dp[0] = 1; dp[1] = 1; // i 表示，序列长度 for (int i = 2; i <= n; i++) { for (int j = 1; j <= i; j++) { dp[i] += dp[j - 1] * dp[i - j]; } } return dp[n]; } ``` ## 98 ```java private boolean flag = true; private TreeNode pre; public boolean isValidBST(TreeNode root) { if (root == null) return true; inOrder(root); return flag; } private void inOrder(TreeNode root) { if (root == null) return; inOrder(root.left); if (pre == null) { pre = root; } else { if (pre.val >= root.val) { flag = false; return; } pre = root; } inOrder(root.right); } ``` ## 99 ```java /** * 中序遍历中的前驱节点 */ private TreeNode prev; /** * 第一个错误节点 */ private TreeNode first; /** * 第二个错误节点 */ private TreeNode second; /** * @param root 是一颗错误的二叉搜索树（有 2 个节点被错误交换） */ public void recoverTree(TreeNode root) { // 1. 找到错误节点 findWrongNodes(root); // 2. 交换 2 个错误节点的值 int tmp = first.val; first.val = second.val; second.val = tmp; } private void findWrongNodes(TreeNode root) { if (root == null) return; findWrongNodes(root.left) ; // 出现了逆序对 if (prev != null && prev.val > root.val) { // 逆序对中较小节点 second = root; // 逆序对中较大节点 if (first != null) return; first = prev; } prev = root; findWrongNodes(root.right); } ``` ## 100 ```java public boolean isSameTree(TreeNode p, TreeNode q) { if (p == null && q == null) { return true; } else if (p == null || q == null) { return false; } else if (p.val != q.val) { return false; } else { return isSameTree(p.left, q.left) && isSameTree(p.right, q.right); } } ``` ## 101 ```java public boolean isSymmetric(TreeNode root) { return isMirror(root, root); } /** * 判断两棵树是否镜像对称 * @param p * @param q * @return */ private boolean isMirror(TreeNode p, TreeNode q) { if (p == null && q == null) return true; if (p == null || q == null) return false; return p.val == q.val && isMirror(p.left, q.right) && isMirror(p.right, q.left); } ``` ## 102 ```java public List> levelOrder(TreeNode root) { List> retList = new ArrayList<>(); if (root == null) return retList; Queue queue = new LinkedList<>(); queue.offer(root); while (!queue.isEmpty()) { List levelList = new ArrayList<>(); int levelSize = queue.size(); for (int i = 0; i< levelSize; i++) { TreeNode cur = queue.poll(); levelList.add(cur.val); if (cur.left != null) queue.offer(cur.left); if (cur.right != null) queue.offer(cur.right); } retList.add(levelList); } return retList; } ``` ## 103 ```java public List> zigzagLevelOrder(TreeNode root) { List> retList = new ArrayList<>(); if (root == null) return retList; /** * true：从左往右遍历 * false：从右像左遍历 */ boolean toggle = true; Queue queue = new LinkedList<>(); queue.offer(root); while (!queue.isEmpty()) { // 数据结构调整 Deque levelList = new LinkedList<>(); int levelSize = queue.size(); for (int i = 0; i < levelSize; i++) { TreeNode cur = queue.poll(); // 每一层数据的添加顺序 if (toggle) { levelList.offerLast(cur.val); } else { levelList.offerFirst(cur.val); } if (cur.left != null) queue.offer(cur.left); if (cur.right != null) queue.offer(cur.right); } retList.add(new ArrayList<>(levelList)); // 修改添加顺序 toggle = !toggle; } return retList; } ``` ## 104 ```java public int maxDepth(TreeNode root) { if (root == null) { return 0; } else { int leftMaxDepth = maxDepth(root.left); int rightMaxDepth = maxDepth(root.right); return Math.max(leftMaxDepth, rightMaxDepth) + 1; } } ``` ## 105 ```java public TreeNode buildTree(int[] preorder, int[] inorder) { int n = preorder.length; // 存储中序遍历值与位置，用于快速定位中序遍历根节点位置 Map iMap = new HashMap<>(); for (int i = 0; i < n; i++) { iMap.put(inorder[i], i); } // 确认好迭代边界很重要（到底是 左闭右开 还是 左闭右闭） return build(preorder, 0, n - 1, inorder, 0, n - 1, iMap); } /** * 根据 preorder[pStart, pEnd] 和 inorder[iStart, iEnd] 创建根节点，并构建子树（将子树连接到根节点） * * 解法：前序遍历 * 提示：前序遍历找到根节点，中序遍历可以获取左右子树大小 * * @param pArray 前序遍历 * @param pStart 前序遍历起始索引 * @param pEnd 前序遍历终止索引 * @param iArray 中序遍历 * @param iStart 中序遍历起始索引 * @param iEnd 中序遍历终止索引 * @param iMap key：中序遍历中的值， val：对应索引 * @return 构建树的根节点 */ public TreeNode build(int[] pArray, int pStart, int pEnd, int[] iArray, int iStart, int iEnd, Map iMap) { if (pStart > pEnd) return null; // 前序遍历中的第一个节点就是根节点 // 获取中序遍历跟节点索引 int iRoot = iMap.get(pArray[pStart]); // 创建根节点 TreeNode root = new TreeNode(pArray[pStart]); // 获取左子树节点数量 int leftSize = iRoot - iStart; // 构造左子树，并连接到根节点 // pStart: 前序遍历，根节点索引 // pStart + 1: 前序遍历，左子树起始位置 // pStart + leftSize: 前序遍历，左子树终止位置 // iStart: 中序遍历，左子树起始位置 // rootIdxInIn: 中序遍历，根节点索引 // rootIdxInIn - 1: 中序遍历，左子树终止位置 root.left = build(pArray, pStart + 1, pStart + leftSize, iArray, iStart, iRoot - 1, iMap); // 构造右子树，并连接到根节点 // pStart: 前序遍历，根节点索引 // pStart + leftSize + 1: 前序遍历，右子树起始位置 // pEnd: 前序遍历，右子树终止位置 // rootIdxInIn + 1: 中序遍历，右子树起始位置 // rootIdxInIn: 中序遍历，根节点索引 // iEnd: 中序遍历，右子树终止位置 root.right = build(pArray, pStart + leftSize + 1, pEnd, iArray, iRoot + 1, iEnd, iMap); return root; } ``` ## 106 ```java public TreeNode buildTree(int[] inorder, int[] postorder) { int n = inorder.length; // 存储中序遍历值与位置，用于快速定位中序遍历根节点位置 Map iMap = new HashMap<>(); for (int i = 0; i < n; i++) { iMap.put(inorder[i], i); } return build(inorder, 0, n - 1, postorder, 0, n - 1, iMap); } /** * * @param iArray * @param iStart * @param iEnd * @param pArray * @param pStart * @param pEnd * @param iMap * @return */ public TreeNode build(int[] iArray, int iStart, int iEnd, int[] pArray, int pStart, int pEnd, Map iMap) { if (iStart > iEnd) return null; int pRoot = pEnd; int iRoot = iMap.get(pArray[pRoot]); int leftSize = iRoot - iStart; TreeNode root = new TreeNode(pArray[pRoot]); root.left = build(iArray, iStart, iRoot - 1, pArray, pStart, pStart + leftSize - 1, iMap); root.right = build(iArray, iRoot + 1, iEnd, pArray, pStart + leftSize, pEnd - 1, iMap); return root; } ``` ## 107 ```java public List> levelOrderBottom(TreeNode root) { List> retList = new LinkedList<>(); if (root == null) return retList; Queue queue = new LinkedList<>(); queue.offer(root); while (!queue.isEmpty()) { List levelList = new ArrayList<>(); int levelSize = queue.size(); for (int i = 0; i < levelSize; i++) { TreeNode cur = queue.poll(); levelList.add(cur.val); if (cur.left != null) queue.offer(cur.left); if (cur.right != null) queue.offer(cur.right); } retList.add(0, levelList); } return retList; } ``` ## 108 ```java public TreeNode sortedArrayToBST(int[] nums) { return build(nums, 0, nums.length - 1); } private TreeNode build(int[] inorder, int start, int end) { if (start > end) return null; int rootIndex = (end + start) / 2; TreeNode root = new TreeNode(inorder[rootIndex]); root.left = build(inorder, start, rootIndex - 1); root.right = build(inorder, rootIndex + 1, end); return root; } ``` ## 109 ```java public TreeNode sortedListToBST(ListNode head) { return build(head, null); } /** * 构造 二叉搜索树 [left, right) * @param left * @param right * @return */ private TreeNode build(ListNode left, ListNode right) { if (left == right) return null; ListNode mid = getMiddle(left, right); TreeNode root = new TreeNode(mid.val); root.left = build(left, mid); root.right = build(mid.next, right); return root; } private ListNode getMiddle(ListNode left, ListNode right) { ListNode fast = left; ListNode slow = left; while (fast != right && fast.next != right) { slow = slow.next; fast = fast.next.next; } return slow; } ``` ## 110 ```java public boolean isBalanced(TreeNode root) { return height(root) >= 0; } /** * 求平衡二叉树的高度，如果返回 -1 表示指定节点不是平衡二叉树 * @param node * @return */ private int height(TreeNode node) { if (node == null) return 0; int leftHeight = height(node.left); int rightHeight = height(node.right); if (leftHeight == -1 || rightHeight == -1 || Math.abs(leftHeight - rightHeight) > 1) return -1; return Math.max(leftHeight, rightHeight) + 1; } ``` ## 111 ```java public int minDepth(TreeNode root) { if (root == null) return 0; // 找到叶子节点才可以返回 if (root.left == null && root.right == null) return 1; // 继续向下查找叶子节点。当前节点至少有一个字节点不为空，为空的子节点不用参与计算 int min = Integer.MAX_VALUE; if (root.left != null) { min = Math.min(min, minDepth(root.left)); } if (root.right != null) { min = Math.min(min, minDepth(root.right)); } return min + 1; } ``` ## 112 ```java public boolean hasPathSum(TreeNode root, int targetSum) { // 终止条件1：root 为空直接返回 false if (root == null) return false; // 终止条件2：找到叶子节点，判断是否满足题目要求 if (root.left == null && root.right == null) return root.val == targetSum; // 左右子树 哪个可以满足条件判断 return hasPathSum(root.left, targetSum - root.val) || hasPathSum(root.right, targetSum - root.val); } ``` ## 113 ```java private List> retList = new LinkedList<>(); public List> pathSum(TreeNode root, int targetSum) { if (root == null) return retList; Deque pathList = new LinkedList<>(); sum(root, targetSum, pathList); return retList; } private void sum(TreeNode node, int targetSum, Deque pathList) { pathList.offerLast(node.val); if (node.left == null && node.right == null && node.val == targetSum) { retList.add(new LinkedList<>(pathList)); } if (node.left != null) { sum(node.left, targetSum - node.val, pathList); } if (node.right != null) { sum(node.right, targetSum - node.val, pathList); } pathList.pollLast(); } ``` ## 114 ```java public void flatten(TreeNode root) { if (root == null) return; // 1. 保留 左右 子节点的引用 TreeNode left = root.left; TreeNode right = root.right; // 2. 将 左子树 插入到 右子树 的地方 root.left = null; root.right = left; // 3. 找到左子树的最右子节点 TreeNode p = root; while (p.right != null) { p = p.right; } // 4. 将原来的右子树接到左子树的最右边节点 p.right = right; flatten(root.left); flatten(root.right); } ``` ## 116 ```java public Node connect(Node root) { if (root == null) return null; connectTwoNode(root.left, root.right); return root; } // 辅助函数 void connectTwoNode(Node node1, Node node2) { if (node1 == null || node2 == null) { return; } /**** 前序遍历位置 ****/ // 将传入的两个节点连接 node1.next = node2; // 连接相同父节点的两个子节点 connectTwoNode(node1.left, node1.right); connectTwoNode(node2.left, node2.right); // 连接跨越父节点的两个子节点 connectTwoNode(node1.right, node2.left); } ``` ## 117 ```java public Node connect(Node root) { if (root == null) return null; Queue queue = new ArrayDeque<>(); queue.offer(root); while (!queue.isEmpty()) { int size = queue.size(); // 取出第一个节点 Node pre = null; for (int i = 0; i < size; i++) { Node curNode = queue.poll(); if (i != 0) { pre.next = curNode; } pre = curNode; if (curNode.left != null) queue.offer(curNode.left); if (curNode.right != null) queue.offer(curNode.right); } } return root; } ``` ## 124 ```java public int maxPathSum(TreeNode root) { maxGain(root); return ans; } /** * 获取当前节点的最大贡献值 * * 前置概念 * 树中最大路径和：从任意节点出发 的最大路径和（可以不包括当前节点），也是本题的解 * 最大贡献值：从当前节点出发 的最大路径和（一定包含当前节点） * * 采用后续遍历，会遍历树中所有节点，并在遍历的过程中求 树中最大路径和。 * 时间复杂度：O(n) * 空间复杂度：O(n) * @param node * @return 当前节点的 最大贡献值 = 当前节点的贡献值 + max(左子节点 最大贡献值, 右子节点 最大贡献值) */ private int maxGain(TreeNode node) { if (node == null) return 0; // 递归计算左右子节点的最大贡献值（如果为负数，返回 0） int leftSum = Math.max(maxGain(node.left), 0); int rightSum = Math.max(maxGain(node.right), 0); // 当前节点的最大贡献值 取决于该节点的值与该节点的左右子节点的 最大贡献值 int curGain = node.val + leftSum + rightSum; // 更新 树中最大路径和 ans = Math.max(ans, curGain); // 返回当前节点的最大贡献值 return node.val + Math.max(leftSum, rightSum); } ``` ## 129 ```java public int sumNumbers(TreeNode root) { return dfs(root, 0); } /** * 返回指定节点的路径和 * @param node 指定节点 * @param preVal 前面路径所形成的数字 * @return */ private int dfs(TreeNode node, int preVal) { if (node == null) return 0; int curVal = preVal * 10 + node.val; if (node.left == null && node.right == null) { return curVal; } else { return dfs(node.left, curVal) + dfs(node.right, curVal); } } ``` ## 144 ### 递归 ```java public List preorderTraversal(TreeNode root) { List ret = new ArrayList<>(); preOrder(root, ret); return ret; } /** * 将前序遍历结果保存在 list 中 * @param node 树节点 * @param list 保存结果的 List */ private void preOrder(TreeNode node, List list) { if (node == null) return; list.add(node.val); preOrder(node.left, list); preOrder(node.right, list); } ``` ### 迭代 ```java public List preorderTraversal(TreeNode root) { List ret = new ArrayList<>(); LinkedList stack = new LinkedList<>(); while (root != null || !stack.isEmpty()) { while (root != null) { ret.add(root.val); stack.push(root); root = root.left; } root = stack.pop(); root = root.right; } return ret; } ``` ### Morris ```java public List preorderTraversal(TreeNode root) { List res = new ArrayList<>(); while (root != null) { // 访问左子树 if (root.left != null) { // p 节点就是当前节点（root）左子树的最右子节点 TreeNode p = root.left; while (p.right != null && p.right != root) { p = p.right; } // 动态添加链接：让 p 的右指针指向 root，继续遍历左子树 if (p.right == null) { // 将当前节点加入答案 res.add(root.val); p.right = root; root = root.left; } // 删除动态链接，回到父节点或访问右子树 if (p.right == root) { p.right = null; root = root.right; } } else { // 如果没有左子树，回到父节点或访问右子树 res.add(root.val); root = root.right; } } return res; } ``` ## 145 ### 递归 ```java private List retList = new ArrayList<>(); public List postorderTraversal(TreeNode root) { postorder(root); return retList; } private void postorder(TreeNode node) { if (node == null) return; postorder(node.left); postorder(node.right); retList.add(node.val); } ``` ### 迭代 ```java public List postorderTraversal(TreeNode root) { List res = new ArrayList<>(); if (root == null) return res; Stack stack = new Stack<>(); TreeNode prev = null; while (root != null || !stack.isEmpty()) { while (root != null) { stack.push(root); root = root.left; } root = stack.pop(); // 当前节点没有右子节点 或者 当前节点的右子节点是它的前驱节点 if (root.right == null || root.right == prev) { res.add(root.val); // 记录前驱节点 prev = root; // 跳过内层 while 循环 root = null; } else { // 重新加入当前节点 stack.push(root); // 先处理右子节点 root = root.right; } } return res; } ``` ## 173 ```java private TreeNode curNode; private Stack stack; public BSTIterator(TreeNode root) { curNode = root; stack = new Stack<>(); } public int next() { while (curNode != null) { stack.push(curNode); curNode = curNode.left; } curNode = stack.pop(); int val = curNode.val; curNode = curNode.right; return val; } public boolean hasNext() { return curNode != null || !stack.isEmpty(); } ``` ## 199 ```java public List rightSideView(TreeNode root) { LinkedList retList = new LinkedList<>(); if (root == null) return retList; Queue queue = new LinkedList<>(); queue.offer(root); while (!queue.isEmpty()) { int size = queue.size(); int lastIndex = size - 1; for (int i = 0; i < size; i++) { TreeNode curNode = queue.poll(); if (i == lastIndex) retList.add(curNode.val); if (curNode.left != null) queue.offer(curNode.left); if (curNode.right != null) queue.offer(curNode.right); } } return retList; } ``` ## 222 ```java public int countNodes(TreeNode root) { if (root == null) return 0; // 求树的层高 int level = 0; TreeNode node = root; while (node.left != null) { level++; node = node.left; } // 在 [low, high] 的范围内进行二分查找 int low = 1 << level, high = (1 << (level + 1)) - 1; while (low < high) { int mid = (high - low + 1) / 2 + low; if (exists(root, level, mid)) { low = mid; } else { high = mid - 1; } } return low; } private boolean exists(TreeNode root, int level, int k) { int bits = 1 << (level - 1); TreeNode node = root; while (node != null && bits > 0) { if ((bits & k) == 0) { node = node.left; } else { node = node.right; } bits >>= 1; } return node != null; } ``` ## 最大正方形（221） ```java int maxSide = 0; int rows = matrix.length, columns = matrix[0].length; // dp[i][j] 表示，以 （i, j） 为右下角的最大正方形边长 int[][] dp = new int[rows][columns]; for (int i = 0; i < rows; i++) { for (int j = 0; j < columns; j++) { if (matrix[i][j] == '1') { // 0 行 0 列的最大边长就是 1 if (i == 0 || j == 0) { dp[i][j] = 1; } else { // 递推公司 dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1; } maxSide = Math.max(maxSide, dp[i][j]); } } } return maxSide * maxSide; ``` ## 226 ```java public TreeNode invertTree(TreeNode root) { if (root == null) return null; TreeNode tmp = root.left; root.left = root.right; root.right = tmp; invertTree(root.left); invertTree(root.right); return root; } ``` ## 230 ```java public int kthSmallest(TreeNode root, int k) { LinkedList stack = new LinkedList<>(); while (root != null || !stack.isEmpty()) { while (root != null) { stack.push(root); root = root.left; } root = stack.pop(); --k; if (k == 0) { break; } root = root.right; } return root.val; } ``` ## 数字 1 的个数（233） ```java public int countDigitOne(int n) { // ten_k 就是 10^k。表示，统计各数位上 1 出现的次数。默认为 1 表示统计 个位 1 出现的次数 long ten_k = 1; int cnt = 0; while (n >= ten_k) { // 计算 高位 1 出现的次数 long h = (n / (ten_k * 10)) * ten_k; // 计算 低位 1 出现的次数 long l = Math.min(Math.max(n % (ten_k * 10) - ten_k + 1, 0), ten_k); cnt += h + l; // 每次 * 10 分别表示统计 10 位 100 位 1 出现的次数， ten_k *= 10; } return cnt; } ``` ## 二叉搜索树的最近公共祖先（235） ```java public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { TreeNode lca = root; while (lca != null) { if (lca.val < p.val && lca.val < q.val) { // 走到这里表示，当前节点的值 小于 p 和 q 的值，说明 p 和 q 应该在当前节点的右子树 lca = lca.right; } else if (lca.val > p.val && lca.val > q.val) { // 走到这里表示，当前节点的值 大于 p 和 q 的值，说明 p 和 q 应该在当前节点的左子树 lca = lca.left; } else { // 走到这里表示，当前节点就是「分岔点」 // 此时，p 和 q 要么在当前节点的不同的子树中，要么其中一个就是当前节点 break; } } return lca; } ``` ## 二叉树的最近公共祖先（236） ```java private TreeNode ans = null; public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { dfs(root, p, q); return ans; } /** * 给定节点的子树中是否包含 p 或 q * @param node * @param p * @param q * @return */ private boolean dfs(TreeNode node, TreeNode p, TreeNode q) { if (node == null) return false; boolean lson = dfs(node.left, p, q); boolean rson = dfs(node.right, p, q); // lson && rson == true 表示，p 和 q 分散在 左右子树中 // (node.val == p.val || node.val == q.val) && (lson || rson) 表示，(node == p || q) && 它的左子树或右子树有一个包含了另一个节点 if ((lson && rson) || ((node.val == p.val || node.val == q.val) && (lson || rson))) { ans = node; } return lson || rson || (node.val == p.val || node.val == q.val); } ``` ## 为运算表达式设计优先级（241） ```java static final int ADD = -1; static final int SUB = -2; static final int MUL = -3; public List diffWaysToCompute(String expression) { // 将 expression 中的 数字 和 运算符 放入 ops 中 List ops = new ArrayList<>(); for (int i = 0; i < expression.length();) { // 运算符，+ - * if (!Character.isDigit(expression.charAt(i))) { if (expression.charAt(i) == '+') { ops.add(ADD); } else if (expression.charAt(i) == '-') { ops.add(SUB); } else { ops.add(MUL); } i++; } else { int num = 0; // 处理数字 while (i < expression.length() && Character.isDigit(expression.charAt(i))) { num = num * 10 + expression.charAt(i) - '0'; i++; } ops.add(num); } } // dp[i][j] 表示，从 i 到 j 按不同优先级组合 数字 和 运算符（它们都存储在 ops 中），所有组合的结果 List[][] dp = new List[ops.size()][ops.size()]; // 初始化 dp 数组，处理 长度为 1 的表达式 for (int i = 0; i < ops.size(); i++) { for (int j = 0; j < ops.size(); j++) { dp[i][j] = new ArrayList<>(); } } // for (int i = 0; i < ops.size(); i += 2) { dp[i][i].add(ops.get(i)); } // 迭代长度从 [3, ops.size] 的 运算表达式，其中 i 表示，运算表达式长度 for (int i = 3; i <= ops.size(); i += 2) { // l 表示，运算表达式左侧起始位置 for (int l = 0; l + i <= ops.size(); l += 2) { // r 表示，运算表达式右侧终止位置 int r = l + i - 1; // k 表示，运算表达式 [l, r] 中的每个 运算符 的位置 for (int k = l + 1; k < r; k += 2) { // 获取 左边 所有组合的结果 List left = dp[l][k - 1]; // 获取 右边 所有组合的结果 List right = dp[k + 1][r]; // 将左右结果合并 for (int num1 : left) { for (int num2 : right) { if (ops.get(k) == ADD) { dp[l][r].add(num1 + num2); } else if (ops.get(k) == SUB) { dp[l][r].add(num1 - num2); } else if (ops.get(k) == MUL) { dp[l][r].add(num1 * num2); } } } } } } return dp[0][ops.size() - 1]; } ``` ## 二叉树的所有路径（257） ```java private List ansList = new LinkedList<>(); public List binaryTreePaths(TreeNode root) { dfs(root, ""); return ansList; } private void dfs(TreeNode node, String path) { if (node != null) { StringBuilder sb = new StringBuilder(path); sb.append(node.val); if (node.left == null && node.right == null) { // 当前节点是叶子节点 ansList.add(sb.toString()); // 把路径加入到答案中 } else { sb.append("->"); // 当前节点不是叶子节点，继续递归遍历 dfs(node.left, sb.toString()); dfs(node.right, sb.toString()); } } } ``` ## 丑数 II（264） ```java public int nthUglyNumber(int n) { // dp[i] 表示，第 i 个丑数 int[] dp = new int[n + 1]; // 最下的丑数是 1 dp[1] = 1; // 定义 三个 指针 int p2 = 1, p3 = 1, p5 = 1; for (int i = 2; i <= n; i++) { int num2 = dp[p2] * 2, num3 = dp[p3] * 3, num5 = dp[p5] * 5; dp[i] = Math.min(Math.min(num2, num3), num5); if (dp[i] == num2) { p2++; } if (dp[i] == num3) { p3++; } if (dp[i] == num5) { p5++; } } return dp[n]; } ``` ## 完全平方数（279） ```java public int numSquares(int n) { // dp[i] 表示，最少需要多少个完全平方数相加和为 i int[] dp = new int[n + 1]; for (int i = 1; i <= n; i++) { // 默认，数字 i 就是由 i 个 1 相加 dp[i] = i; for (int j = 1; j * j <= i; j++) { // 递推公式 dp[i] = Math.min(dp[i], dp[i - j * j] + 1) ; } } return dp[n]; } ``` ## 二叉树的序列化与反序列化（297） ```java public String serialize(TreeNode root) { return serialize(root, ""); } private String serialize(TreeNode root, String str) { if (root == null) { str = str + "None,"; } else { str = str + root.val + ","; str = serialize(root.left, str); str = serialize(root.right, str); } return str; } /** * 先序遍历顺序 * @param data * @return */ // Decodes your encoded data to tree. public TreeNode deserialize(String data) { String[] dataArray = data.split(","); List dataList = new LinkedList<>(Arrays.asList(dataArray)); return rdeserialize(dataList); } private TreeNode rdeserialize(List dataList) { if (dataList.get(0).equals("None")) { dataList.remove(0); return null; } TreeNode root = new TreeNode(Integer.parseInt(dataList.get(0))); dataList.remove(0); root.left = rdeserialize(dataList); root.right = rdeserialize(dataList); return root; } ``` ## 验证二叉树的前序序列化(331) ```java public boolean isValidSerialization(String preorder) { int n = preorder.length(); int i = 0; Stack stack = new Stack<>(); stack.push(1); while (i < n) { // 还有没填充的字符串，但 stack 空了 if (stack.isEmpty()) { return false; } if (preorder.charAt(i) == ',') { // 遇到了分隔符 i++; } else if (preorder.charAt(i) == '#') { // 遇到了空节点 int top = stack.pop() - 1; if (top > 0) { stack.push(top); } i++; } else { // 读一个数字 while (i < n && preorder.charAt(i) != ',') { i++; } int top = stack.pop() - 1; if (top > 0) { stack.push(top); } stack.push(2); } } return stack.isEmpty(); } ``` ## 打家劫舍 III（337） ```java // f(o) 表示选择 o 节点的情况下，o 节点的子树上被选择的节点的最大权值和 // g(o) 表示不选择 o 节点的情况下，o 节点的子树上被选择的节点的最大权值和 // l 和 r 代表 o 的左右孩子 // 1. 当 o 被选中时，o 的左右孩子都不能被选中，故 o 被选中情况下子树上被选中点的最大权值和为 l 和 r 不被选中的最大权值和相加，即 f(o)=g(l)+g(r) // 2. 当 o 不被选中时，o 的左右孩子可以被选中，也可以不被选中。对于 o 的某个具体的孩子 x，它对 o 的贡献是 x 被选中和不被选中情况下权值和的较大值。故 g(o)=max{f(l),g(l)}+max{f(r),g(r)} // f 和 g 哈希表存储每个节点对应的选中和不选中的值 Map f = new HashMap<>(); Map g = new HashMap<>(); public int rob(TreeNode root) { dfs(root); return Math.max(f.getOrDefault(root, 0), g.getOrDefault(root, 0)); } /** * 构造 f 和 g * @param node */ private void dfs(TreeNode node) { if (node == null) return; dfs(node.left); dfs(node.right); f.put(node, node.val + g.getOrDefault(node.left, 0) + g.getOrDefault(node.right, 0)); g.put(node, Math.max(f.getOrDefault(node.left, 0), g.getOrDefault(node.left, 0)) + Math.max(f.getOrDefault(node.right, 0), g.getOrDefault(node.right, 0))); } ``` ## 左叶子之和（404） ```java public int sumOfLeftLeaves(TreeNode root) { if (root == null) return 0; int ret = 0; Queue queue = new LinkedList<>(); queue.offer(root); while (!queue.isEmpty()) { TreeNode curNode = queue.poll(); if (curNode.left != null) { if (isLeafNode(curNode.left)) { ret += curNode.left.val; } else { queue.offer(curNode.left); } } if (curNode.right != null) { queue.offer(curNode.right); } } return ret; } private boolean isLeafNode(TreeNode node) { return node.left == null && node.right == null; } ``` ## 路径总和 III（437） ```java // dfs 时间复杂度：O(n)；空间复杂度：O(n²) /** * 节点值之和等于 targetSum 的 路径 的数目 * @param root * @param targetSum * @return */ public int pathSum(TreeNode root, long targetSum) { if (root == null) return 0; // 以根节点为起始节点 int cnt = dfs(root, targetSum); // 递归处理所有子节点 cnt += pathSum(root.left, targetSum); cnt += pathSum(root.right, targetSum); return cnt; } /** * 返回 以 node 为 起始节点 有多少条路径的和为 targetSum * 注：本函数固定了起始节点 * @param node * @param targetSum * @return */ private int dfs(TreeNode node, long targetSum) { if (node == null) return 0; int ret = 0; int val = node.val; if (targetSum == val) ret++; ret += dfs(node.left, targetSum - val); ret += dfs(node.right, targetSum - val); return ret; } ``` ```java // 前缀和 时间复杂度：O(n)；空间复杂度：O(n) public int pathSum(TreeNode root, long targetSum) { // key 路径和，val 路径和个数 Map prefix = new HashMap<>(); prefix.put(0L, 1); return dfs(root, prefix, 0, targetSum); } /** * 返回以 node 为根的子树中有多少 路径的和为 targetSum * @param node * @param prefix * @param preSum 根节点 到 当前节点的父节点 的路径和 * @param targetSum * @return */ private int dfs(TreeNode node, Map prefix, long preSum, long targetSum) { if (node == null) return 0; // 有多少路径的和为 targetSum int cnt = 0; // 根节点 到 当前节点 的路径和 preSum += node.val; cnt = prefix.getOrDefault(preSum - targetSum, 0); // 更新 路径和 prefix.put(preSum, prefix.getOrDefault(preSum, 0) + 1); cnt += dfs(node.left, prefix, preSum, targetSum); cnt += dfs(node.right, prefix, preSum, targetSum); // 回溯，在遍历完一个节点的所有子节点后，将其从 map 中除去 prefix.put(preSum, prefix.getOrDefault(preSum, 0) - 1); return cnt; } ``` ## 序列化和反序列化二叉搜索树（449） ```java public String serialize(TreeNode root) { List list = new ArrayList<>(); postOrder(root, list); String str = list.toString(); return str.substring(1, str.length() - 1); } private void postOrder(TreeNode node, List list) { if (node == null) return; postOrder(node.left, list); postOrder(node.right, list); list.add(node.val); } // Decodes your encoded data to tree. public TreeNode deserialize(String data) { if (data.isEmpty()) return null; String[] arr = data.split(", "); Deque stack = new ArrayDeque<>(); int length = arr.length; for (int i = 0; i < length; i++) { stack.push(Integer.parseInt(arr[i])); } return construct(Integer.MIN_VALUE, Integer.MAX_VALUE, stack); } private TreeNode construct(int lower, int upper, Deque stack) { if (stack.isEmpty() || stack.peek() < lower || stack.peek() > upper) { return null; } int val = stack.pop(); TreeNode root = new TreeNode(val); root.right = construct(val, upper, stack); root.left = construct(lower, val, stack); return root; } ``` ## 删除二叉搜索树中的节点（450） ```java /** * 从给定根节点的树中删除节点值为 key 的节点，返回 删除后的树的根节点 * @param root * @param key * @return */ public TreeNode deleteNode(TreeNode root, int key) { if (root == null) return null; if (root.val > key) { root.left = deleteNode(root.left, key); return root; } if (root.val < key) { root.right = deleteNode(root.right, key); return root; } if (root.val == key) { // 叶子节点直接删除 if (root.left == null && root.right == null) { return null; } // 右子树为空，直接返回左子树 if (root.right == null) { return root.left; } // 左子树为空，直接返回右子树 if (root.left == null) { return root.right; } // 左右子树都不为空，返回后继节点 TreeNode successor = root.right; while (successor.left != null) { successor = successor.left; } // 在 root 的右子树中删除 successor 节点，返回新的 root 的右子树 root.right = deleteNode(root.right, successor.val); // 用 successor 替换 root 节点 successor.right = root.right; successor.left = root.left; return successor; } return root; } ``` ## 二叉搜索树中的众数（501） ```java // 答案数组 private List answer = new ArrayList<>(); // 当前数字， 当前数字出现次数， 众数次数（出现次数最多的数） private int val, count, maxCount; public int[] findMode(TreeNode root) { // 中序遍历，相同数字会连续出现 dfs(root); return answer.stream().mapToInt(Integer::valueOf).toArray(); } private void dfs(TreeNode node) { if (node == null) return; dfs(node.left); update(node.val); dfs(node.right); } private void update(int val) { // 如果 val 和 this.val 相等则 count + 1 if (val == this.val) { count++; } else { // 否则，重置 count 并将 val 赋值给 this.val count = 1; this.val = val; } // 如果 count 等于 maxCount 将 val 加入 answer if (count == maxCount) { answer.add(val); } // 如果 count 大于 maxCount 将 answer 清空，并将 val 加入 answer if (count > maxCount) { maxCount = count; answer.clear(); answer.add(val); } } ``` ## 出现次数最多的子树元素和（508） ```java // key: 子树元素和, val: 出现次数 private Map countMap = new HashMap<>(); // 最大次数 private int maxCount = 0; public int[] findFrequentTreeSum(TreeNode root) { dfs(root); List retList = new ArrayList<>(); for (Map.Entry entry : countMap.entrySet()) { int key = entry.getKey(); int val = entry.getValue(); if (maxCount == val) { retList.add(key); } } return retList.stream().mapToInt(Integer::valueOf).toArray(); } private int dfs(TreeNode node) { if (node == null) return 0; int sum = node.val + dfs(node.left) + dfs(node.right); countMap.put(sum, countMap.getOrDefault(sum, 0) + 1); maxCount = Math.max(maxCount, countMap.get(sum)); return sum; } ``` ## 找树左下角的值（513） ```java public int findBottomLeftValue(TreeNode root) { Deque deque = new LinkedList<>(); deque.offer(root); int val = 0; while (!deque.isEmpty()) { int size = deque.size(); for (int i = 0; i < size; i++) { TreeNode curNode = deque.poll(); if (i == 0) { val = curNode.val; } if (curNode.left != null) deque.offer(curNode.left); if (curNode.right != null) deque.offer(curNode.right); } } return val; } ``` ## 在每个树行中找最大值（515） ```java public List largestValues(TreeNode root) { if (root == null) return new ArrayList<>(); Deque deque = new LinkedList<>(); deque.offer(root); List retList = new ArrayList<>(); while (!deque.isEmpty()) { int size = deque.size(); int maxVal = Integer.MIN_VALUE; for (int i = 0; i < size; i++) { TreeNode curNode = deque.poll(); if (curNode.left != null) deque.offer(curNode.left); if (curNode.right != null) deque.offer(curNode.right); maxVal = Math.max(maxVal, curNode.val); } retList.add(maxVal); } return retList; } ``` ## 二叉搜索树的最小绝对差（530） ```java private int preVal = -1; private int minSub = Integer.MAX_VALUE; public int getMinimumDifference(TreeNode root) { dfs(root); return minSub; } private void dfs(TreeNode node) { if (node == null) return; dfs(node.left); update(node.val); dfs(node.right); } private void update(int val) { if (preVal != -1) { minSub = Math.min((val - preVal), minSub); } preVal = val; } ``` ## 把二叉搜索树转换为累加树（538） ```java int sum = 0; /** * 反向中序遍历累加 * @param root * @return */ public TreeNode convertBST(TreeNode root) { if (root != null) { convertBST(root.right); sum += root.val; root.val = sum; convertBST(root.left); } return root; } ``` ## 二叉树的直径（543） ```java private int ans = 0; public int diameterOfBinaryTree(TreeNode root) { ans = 1; depth(root); // 树的直径 = 经过的节点数 - 1 return ans - 1; } /** * 获取指定节点高度(树的高度也是经过的节点数) * @param node * @return */ private int depth(TreeNode node) { if (node == null) return 0; int L = depth(node.left); int R = depth(node.right); // ans = Math.max(ans, L + R + 1); return Math.max(L, R) + 1; } ``` ## 二叉树的坡度（563） ```java private int ans = 0; public int findTilt(TreeNode root) { if (root == null) return 0; dfs(root); return ans; } /** * 获取已给定节点为根的树中所有节点之和 * @param node * @return */ private int dfs(TreeNode node) { if (node == null) return 0; int L = dfs(node.left); int R = dfs(node.right); ans += Math.abs(L - R); return L + R + node.val; } ``` ## 另一棵树的子树（572） ```java public boolean isSubtree(TreeNode root, TreeNode subRoot) { return dfs(root, subRoot); } /** * 判断 node 中是否包含和 sub 具有相同结构和节点值的子树 * @param node * @param sub * @return */ private boolean dfs(TreeNode node, TreeNode sub) { if (node == null) return false; return check(node, sub) || dfs(node.left, sub) || dfs(node.right, sub); } /** * 判断给定的 s 和 t 是否是完全相等的二叉树 * @param s * @param t * @return */ private boolean check(TreeNode s, TreeNode t) { if (s == null && t == null) return true; if (s == null || t == null || s.val != t.val) return false; return check(s.left, t.left) && check(s.right, t.right); } ``` ## 根据二叉树创建字符串（606） ```java /** * 此题需要考虑 4 种情况 * 1. 如果当前节点有两个孩子，那我们在递归时，需要在两个孩子的结果外都加上一层括号； * 2. 如果当前节点没有孩子，那我们不需要在节点后面加上任何括号 * 3. 如果当前节点只有左孩子，那我们在递归时，只需要在左孩子的结果外加上一层括号，而不需要给右孩子加上任何括号 * 4. 如果当前节点只有右孩子，那我们在递归时，需要先加上一层空的括号 ‘()’ 表示左孩子为空，再对右孩子进行递归，并在结果外加上一层括号 * @param root * @return */ public String tree2str(TreeNode root) { if (root == null) return ""; if (root.left == null && root.right == null) return String.valueOf(root.val); // 如果右子节点为空，只需要递归左子节点。节省了对右子节点的递归 if (root.right == null) { return root.val + "(" + tree2str(root.left) + ")"; } // 右子节点不空， return root.val + "(" + tree2str(root.left) + ")" + "(" + tree2str(root.right) + ")"; } ``` ## 合并二叉树（617） ```java public TreeNode mergeTrees(TreeNode root1, TreeNode root2) { if (root1 == null) return root2; if (root2 == null) return root1; // 走到这里 root1 和 root2 都不为空 // 合并 root1 和 root2 的左子树，并将结果设置到 root1 中 root1.left = mergeTrees(root1.left, root2.left); // 合并 root1 和 root2 的右子树，并将结果设置到 root1 中 root1.right = mergeTrees(root1.right, root2.right); // 将 root2 合并到 root1 root1.val = root1.val + root2.val; return root1; } ``` ## 在二叉树中增加一行（623） ```java public TreeNode addOneRow(TreeNode root, int val, int depth) { if (depth == 1) { return new TreeNode(val, root, null); } Deque deque = new LinkedList<>(); deque.offer(root); int curDepth = 1; while (!deque.isEmpty()) { curDepth++; if (curDepth == depth) break; int size = deque.size(); for (int i = 0; i < size; i++) { TreeNode node = deque.poll(); if (node.left != null) deque.offer(node.left); if (node.right != null) deque.offer(node.right); } } while (!deque.isEmpty()) { TreeNode node = deque.poll(); node.left = new TreeNode(val, node.left, null); node.right = new TreeNode(val, null, node.right); } return root; } ``` ## 二叉树的层平均值（637） ```java List retList = new LinkedList<>(); Deque deque = new LinkedList<>(); deque.offer(root); while (!deque.isEmpty()) { int size = deque.size(); double sum = 0; TreeNode node; for(int i = 0; i < size; i++) { node = deque.poll(); sum += node.val; if (node.left != null) deque.offer(node.left); if (node.right != null) deque.offer(node.right); } retList.add(sum/size); } return retList; ``` ## 寻找重复的子树（652） ```java // key 序列化后的子树字符串，val 出现次数 Map memo = new HashMap<>(); // 重复子树的根节点 List res = new LinkedList<>(); public List findDuplicateSubtrees(TreeNode root) { serialize(root); return res; } /** * 序列化以 node 为根节点的树 * 采用后续遍历的方式 * # 表示空节点 * @param node * @return */ private String serialize(TreeNode node) { if (node == null) return "#"; String left = serialize(node.left); String right = serialize(node.right); String subTree = left + "," + right + "," + node.val; // freq 表示，出现次数 int freq = memo.getOrDefault(subTree, 0); if (freq == 1) res.add(node); memo.put(subTree, freq + 1); return subTree; } ``` ## 两数之和 IV - 输入二叉搜索树（653） ```java public boolean findTarget(TreeNode root, int k) { List list = new ArrayList<>(); inorder(root, list); int l = 0; int r = list.size() - 1; while (l < r) { if ((list.get(l) + list.get(r)) > k) { r--; } else if((list.get(l) + list.get(r)) < k) { l++; } else { return true; } } return false; } private void inorder(TreeNode node, List list) { if (node == null) return; inorder(node.left, list); list.add(node.val); inorder(node.right, list); } ``` ## 最大二叉树（654） ```java public TreeNode constructMaximumBinaryTree(int[] nums) { if (nums == null) return null; return findRoot(nums, 0, nums.length); } /** * 找出 [l, r) 范围的根节点 * @param nums * @param l * @param r * @return */ private TreeNode findRoot(int[] nums, int l, int r) { if (l == r) return null; // 找出 [l, r) 范围内最大值的索引 int maxIdx = l; for (int i = l + 1; i < r; i++) { if (nums[i] > nums[maxIdx]) maxIdx = i; } TreeNode root = new TreeNode(nums[maxIdx]); root.left = findRoot(nums, l, maxIdx); root.right = findRoot(nums, maxIdx + 1, r);; return root; } ``` ## 输出二叉树（655） ```java public List> printTree(TreeNode root) { // 计算树的高度 int height = calDepth(root); // 矩阵的行数 int m = height + 1; // 矩阵的列数 int n = (1 << (height + 1)) - 1; // 结果矩阵 List> res = new ArrayList<>(); // 初始化结果矩阵 for (int i = 0; i < m; i++) { List row = new ArrayList<>(); for (int j = 0; j < n; j++) { row.add(""); } res.add(row); } // 广度优先设置矩阵 Queue queue = new LinkedList<>(); queue.offer(new Tuple(root, 0, (n - 1) / 2)); while (!queue.isEmpty()) { Tuple tuple = queue.poll(); TreeNode node = tuple.node; int r = tuple.r; int c = tuple.c; res.get(r).set(c, Integer.toString(node.val)); if (node.left != null) { queue.offer(new Tuple(node.left, r + 1, c - (1 << (height - r - 1)))); } if (node.right != null) { queue.offer(new Tuple(node.right, r + 1, c + (1 << (height - r - 1)))); } } return res; } public int calDepth(TreeNode root) { int ret = -1; Queue queue = new LinkedList<>(); queue.offer(root); while (!queue.isEmpty()) { ret++; int size = queue.size(); while (size > 0) { size--; TreeNode node = queue.poll(); if (node.left != null) queue.offer(node.left); if (node.right != null) queue.offer(node.right); } } return ret; } private class Tuple { private TreeNode node; private int r; private int c; public Tuple(TreeNode node, int r, int c) { this.node = node; this.r = r; this.c = c; } } ``` ## 二叉树最大宽度（662） ```java public int widthOfBinaryTree(TreeNode root) { // 最大宽度 int ans = 1; // Pair 中存储着当前节点和节点对应编号 List> arr = new LinkedList<>(); arr.add(new Pair<>(root, 1)); while (!arr.isEmpty()) { int size = arr.size(); List> tmp = new LinkedList<>(); // 每一层的宽度 = 最右节点编号 - 最左节点编号 + 1 int wide = arr.get(size - 1).getValue() - arr.get(0).getValue() + 1; // 更新二叉树最大宽度 ans = Math.max(ans, wide); // 遍历当前层 for (int i = 0; i < size; i++) { Pair pair = arr.get(i); TreeNode node = pair.getKey(); Integer index = pair.getValue(); if (node.left != null) { // 满二叉树左子节点序号 = 父节点序号 * 2 tmp.add(new Pair<>(node.left, index * 2)); } if (node.right != null) { // 满二叉树右子节点序号 = 父节点序号 * 2 + 1 tmp.add(new Pair<>(node.right, index * 2 + 1)); } } arr = tmp; } return ans; } ``` ## 修剪二叉搜索树（669） ```java /** * 返回对指定节点剪切后的结果 * @param root 指定节点 * @param low 节点取值范围的最小值 * @param high 节点取值范围的最大值 * @return */ public TreeNode trimBST(TreeNode root, int low, int high) { if (root == null) { return null; } if (root.val < low) { // 如果当前节点的值小于 low，那么说明当前结点及它的左子树都不符合要求，我们返回对它的右子结点进行修剪后的结果 return trimBST(root.right, low, high); } else if (root.val > high) { // 如果当前节点的值大于 high，那么说明当前结点及它的右子树都不符合要求，我们返回对它的左子结点进行修剪后的结果 return trimBST(root.left, low, high); } else { // 如果结点的值位于区间 [low,high]，我们将结点的左子结点设为对它的左子树修剪后的结果，右结点设为对它的右子树进行修剪后的结果 root.left = trimBST(root.left, low, high); root.right = trimBST(root.right, low, high); return root; } } ``` ## 二叉树中第二小的节点（671） ```java private int ans; private int rootVal; public int findSecondMinimumValue(TreeNode root) { ans = -1; rootVal = root.val; dfs(root); return ans; } public void dfs(TreeNode node) { if (node == null) return; // 以当前节点为根的子树中所有节点都大于当前节点，相当于剪枝操作。节省不必要的循环 if (ans != -1 && node.val >= ans) return; // 更新答案 if (node.val > rootVal) ans = node.val; dfs(node.left); dfs(node.right); } ``` ## 最长同值路径（687） ```java // 最长路径 private int maxRes; public int longestUnivaluePath(TreeNode root) { maxRes = 0; dfs(root); return maxRes; } /** * 获取指定节点的最长同值路径 * 定义：同值有向路径为从某一结点出发，到达它的某一后代节点的路径，且经过的结点的值相同 * @param node 指定节点 * @return 返回 最长同值路径 */ public int dfs(TreeNode node) { if (node == null) return 0; // 获取节点的左右 最长同值路径 int lMax = dfs(node.left); int rMax = dfs(node.right); int lRet = 0; int rRet = 0; if (node.left != null && node.left.val == node.val) { lRet = lMax + 1; } if (node.right != null && node.right.val == node.val) { rRet = rMax + 1; } maxRes = Math.max(maxRes, lRet + rRet); return Math.max(lRet, rRet); } ``` ## 二叉搜索树中的搜索（700） ```java public TreeNode searchBST(TreeNode root, int val) { while (root != null) { if (val == root.val) return root; root = val < root.val ? root.left : root.right; } return null; } ``` ## 二叉搜索树中的插入操作（701） ```java public TreeNode insertIntoBST(TreeNode root, int val) { if (root == null) return new TreeNode(val); dfs(root, val); return root; } /** * 在已 node 为根的树中插入 val * @param node * @param val */ private void dfs(TreeNode node, int val) { if (node.val > val) { if (node.left != null) { dfs(node.left, val); } else { node.left = new TreeNode(val); } } else { if (node.right != null) { dfs(node.right, val); } else { node.right = new TreeNode(val); } } } ``` ## 数据流中的第 K 大元素（703） ```java // 小顶堆（堆顶元素最小） private PriorityQueue pq; private int k; public _703_数据流中的第K大元素(int k, int[] nums) { this.k = k; pq = new PriorityQueue<>(); for (int x : nums) { add(x); } } public int add(int val) { // 插入元素 pq.offer(val); if (pq.size() > k) { // 返回队顶元素（队列中最小的元素） pq.poll(); } return pq.peek(); } ``` ## 二叉搜索树节点最小距离（783） ```java // 最小差值 private int min = Integer.MAX_VALUE; // 前继节点值 private int pre = -1; public int minDiffInBST(TreeNode root) { // 迭代终止条件，null 节点不参与计算 if (root == null) return min = Integer.MAX_VALUE; if (root.left != null) { minDiffInBST(root.left); } if (pre == -1) { pre = root.val; } else { min = Math.min(min, root.val - pre); pre = root.val; } if (root.right != null) { minDiffInBST(root.right); } return min; } ``` ## 二叉树剪枝（814） ```java public TreeNode pruneTree(TreeNode root) { if (root == null) return null; root.left = pruneTree(root.left); root.right = pruneTree(root.right); if (root.left == null && root.right == null && root.val == 0) return null; return root; } ``` ## 二叉树中所有距离为 K 的结点（863） ```java // key: 节点值，val: 父节点 private Map parentMap = new HashMap<>(); private List ans = new ArrayList<>(); public List distanceK(TreeNode root, TreeNode target, int k) { getParentMap(root); getAns(target, null, 0, k); return ans; } /** * 构造 parentMap * @param node */ private void getParentMap(TreeNode node) { if (node.left != null) { parentMap.put(node.left.val, node); getParentMap(node.left); } if (node.right != null) { parentMap.put(node.right.val, node); getParentMap(node.right); } } /** * 从 node 节点出发，寻找距离 node 节点深度为 k 的节点 * @param node 出发节点 * @param fromNode 防止重复递归（尤其是从子向父递归的时候） * @param depth 当前深度 * @param k 目标深度 */ private void getAns(TreeNode node, TreeNode fromNode, int depth, int k) { if (node == null) return; if (depth == k) { ans.add(node.val); return; } // 遍历目标节点的左右子树 // 从题目中给定的 target 节点出发向上走时，防止重复遍历 target 节点 if (node.left != fromNode) { getAns(node.left, node, depth + 1, k); } if (node.right != fromNode) { getAns(node.right, node, depth + 1, k); } // 遍历目标节点的父节点 // 向下遍历二叉树时，防止重复递归父节点 if (parentMap.get(node.val) != fromNode) { getAns(parentMap.get(node.val), node, depth + 1, k); } } ``` ## 具有所有最深节点的最小子树（865） ```java public TreeNode subtreeWithAllDeepest(TreeNode root) { return dfs(root).getKey(); } /** * 深度优先计算 Pair（key: 以传入的 node 节点为根的子树中，所有最深节点的最近公共祖先, val: 以传入的 node 节点为根的子树的最大深度） * @param * @return */ private Pair dfs(TreeNode node) { if (node == null) return new Pair<>(node, 0); Pair l = dfs(node.left); Pair r = dfs(node.right); // 左子树的最大深度 int lDepth = l.getValue(); // 右子树的最大深度 int rDepth = r.getValue(); // 左子树更深，所有最深节点的最小子树在左子树中 if (lDepth > rDepth) return new Pair<>(l.getKey(), lDepth + 1); // 右子树更深，所有最深节点的最小子树在右子树中 if (lDepth < rDepth) return new Pair<>(r.getKey(), rDepth + 1); // 左右子树一样深，当前节点 node 就是所有最深节点的最小子树的根 return new Pair<>(node, lDepth + 1); } ``` ## 叶子相似的树（872） ```java public boolean leafSimilar(TreeNode root1, TreeNode root2) { List r1List = new ArrayList<>(); List r2List = new ArrayList<>(); dfs(root1, r1List); dfs(root2, r2List); return r1List.equals(r2List); } /** * 从左到右依次寻找叶子节点 * @param node * @param list */ private void dfs(TreeNode node, List list) { if (node == null) return; if (node.left == null && node.right == null) { list.add(node.val); } else { dfs(node.left, list); dfs(node.right, list); } } ``` ## 根据前序和后序遍历构造二叉树（889） ```java public TreeNode constructFromPrePost(int[] preorder, int[] postorder) { int n = preorder.length; // key: 元素值, val: 元素索引 Map postMap = new HashMap<>(); for (int i = 0; i < n; i++) { postMap.put(postorder[i], i); } return dfs(preorder, postorder, postMap, 0, n - 1, 0, n - 1); } /** * 给定 前序遍历（preorder）和 后序遍历（postorder）的数组，以及索引区间（闭区间 ）构建二叉树 * @param preorder * @param postorder * @param postMap * @param preLeft * @param preRight * @param postLeft * @param postRight * @return */ public TreeNode dfs(int[] preorder, int[] postorder, Map postMap, int preLeft, int preRight, int postLeft, int postRight) { // 闭区间，终止条件是 preLeft > preRight if (preLeft > preRight) return null; // 计算左子树有多少个节点 int leftCount = 0; // 如果 preLeft == preRight 表示，只有根节点。所以，左子树有 0 个节点，无需计算 if (preLeft < preRight) { // preLeft + 1 表示左子树的根节点 // 例如，如果最终的二叉树可以被序列化的表述为 [1, 2, 3, 4, 5, 6, 7] // 那么其前序遍历为 [1] + [2, 4, 5] + [3, 6, 7]，而后序遍历为 [4, 5, 2] + [6, 7, 3] + [1] leftCount = postMap.get(preorder[preLeft + 1]) - postLeft + 1; } return new TreeNode(preorder[preLeft], // 构建左子树 dfs(preorder, postorder, postMap, preLeft + 1, preLeft + leftCount, postLeft, postLeft + leftCount - 1), // 构建右子树 dfs(preorder, postorder, postMap, preLeft + leftCount + 1, preRight, postLeft + leftCount, postRight - 1)); } ``` ## 所有可能的真二叉树(894) ### 分治 ```java public List allPossibleFBT(int n) { List fbtList = new ArrayList<>(); // 由于，真二叉树中的每个结点的子结点数是 0 或 2。所以，真二叉树节点数量一定是奇数 // 如果节点数是偶数直接返回 if (n % 2 == 0) return fbtList; // n == 1 表示，只有一个根节点 if (n == 1) { fbtList.add(new TreeNode(0)); return fbtList; } // 走到这里表示，n 是奇数并且大于 1 // n 个节点构建的二叉树，左右子树节点数量序列为 // [(1,n−2),(3,n−4),(5,n−6),⋯,(n−2,1)] for (int i = 1; i < n; i += 2) { // i 表示左子树节点数，n - 1 - i 就是右子树节点数 // 返回所有可能的左子树 List leftSubtrees = allPossibleFBT(i); // 返回所有可能的右子树 List rightSubtrees = allPossibleFBT(n - 1 - i); // 遍历左右子树构建二叉树 for (TreeNode leftSubtree : leftSubtrees) { for (TreeNode rightSubtree : rightSubtrees) { TreeNode root = new TreeNode(0, leftSubtree, rightSubtree); fbtList.add(root); } } } return fbtList; } ``` ### 动态规划 在题目给定的真二叉树中，一个节点要么有 0 个子节点，要么有 2 个子节点。当只有一个节点的时候，也就是树中节点数目最少的时候。此时，树中只有根节点。当增加节点时，只能增加 0 或 2 个。所以树中节点总数一定是奇数。 那么，节点数为 n 的真二叉树有多少种情况，取决于选定根节点后，它的左右子树各有多少种情况。此时，左子树的节点数为 j，右子树的节点数量就是 n - 1 - j。原问题的规模变小了。我们知道当 j 等于 1 时，只有一种情况 ```java public List allPossibleFBT(int n) { // 由于，真二叉树中的每个结点的子结点数是 0 或 2。所以，真二叉树节点数量一定是奇数 // 如果节点数是偶数直接返回 if (n % 2 == 0) return new ArrayList<>(); // dp 数组索引表示节点总数，值表示 这些节点可以构成的所有真二叉树 List[] dp = new ArrayList[n + 1]; for (int i = 0; i <= n; i++) { dp[i] = new ArrayList<>(); } dp[1].add(new TreeNode(0)); // 节点总数从 3 到 n 递推 for (int i = 3; i <= n; i += 2) { // j 表示，左子树节点数 for (int j = 1; j < i; j += 2) { // 遍历左右子树构建二叉树 for (TreeNode leftSubtree : dp[j]) { for (TreeNode rightSubtrees : dp[i - 1 - j]) { TreeNode root = new TreeNode(0, leftSubtree, rightSubtrees); dp[i].add(root); } } } } return dp[n]; } ``` ## 递增顺序搜索树(897) ```java private TreeNode dummyPointer; public TreeNode increasingBST(TreeNode root) { // 创建虚拟节点 TreeNode dummyNode = new TreeNode(-1); // dummyPointer 是虚拟节点的指针，在中序遍历中不断变换 dummyPointer = dummyNode; inorder(root); return dummyNode.right; } private void inorder(TreeNode node) { if (node == null) return; inorder(node.left); // 不断修改 dummyPointer dummyPointer.right = node; dummyPointer = node; node.left = null; inorder(node.right); } ``` ## 完全二叉树插入器(919) ### 层序遍历 ```java // 可以插入子节点的父节点 private Queue queue; private TreeNode root; public _919_完全二叉树插入器_层序遍历(TreeNode root) { this.root = root; this.queue = new LinkedList<>(); Queue travelQueue = new LinkedList<>(); travelQueue.offer(root); while (!travelQueue.isEmpty()) { int size = travelQueue.size(); TreeNode curNode; for (int i = 0; i < size; i++) { curNode = travelQueue.poll(); if (curNode.left != null) travelQueue.offer(curNode.left); if (curNode.right != null) travelQueue.offer(curNode.right); // 只要节点的右指针为空，它就是可以插入子节点的父节点（insert 中会判断，插入左边还是右边） if (curNode.right == null) { this.queue.offer(curNode); } } } } public int insert(int val) { TreeNode newNode = new TreeNode(val); TreeNode parentNode = this.queue.peek(); int ret = parentNode.val; if (parentNode.left == null) { parentNode.left = newNode; } else { parentNode.right = newNode; this.queue.poll(); } this.queue.offer(newNode); return ret; } public TreeNode get_root() { return this.root; } ``` ### 二进制表示 ```java private int count; private TreeNode root; public _919_完全二叉树插入器_二进制表示(TreeNode root) { this.count = 0; this.root = root; Queue queue = new LinkedList<>(); queue.offer(root); while (!queue.isEmpty()) { this.count++; TreeNode curNode = queue.poll(); if (curNode.left != null) queue.offer(curNode.left); if (curNode.right != null) queue.offer(curNode.right); } } public int insert(int val) { this.count++; TreeNode newNode = new TreeNode(val); TreeNode node = root; // hightbit 表示有效数字位数 = 32（int 类型总长度） - count 有多少个前导零 int hightbit = 32 - Integer.numberOfLeadingZeros(count); // 根据二进制数判断节点走左子节点还是右子节点时，第一位不参与计算 -1 // 由于 1 << 1 = 10，左移一位就在第二位了，所以再 -1 // 所以 i = hightbit - 2，从第二位开始判断 // 最后一位没有路径了不需要判断，所以 i >= 1 for (int i = hightbit - 2; i >= 1; i--) { if ((count & (1 << i)) == 0) { node = node.left; } else { node = node.right; } } if ((count & 1) == 0) { node.left = newNode; } else { node.right = newNode; } return node.val; } public TreeNode get_root() { return this.root; } ``` ## 二叉搜索树的范围和（938） ### 广度优先 ```java public int rangeSumBST(TreeNode root, int low, int high) { int sum = 0; Queue queue = new LinkedList<>(); queue.offer(root); while (!queue.isEmpty()) { TreeNode node = queue.poll(); if (node == null) continue; if (node.val > high) { // 当前节点值太大，在左子树查找 queue.offer(node.left); } else if(node.val < low) { // 当前节点值太小，在右子树查找 queue.offer(node.right); } else { // 当前节点值在查找范围内 [low, high] sum += node.val; queue.offer(node.left); queue.offer(node.right); } } return sum; } ``` ### 深度优先 ```java public int rangeSumBST(TreeNode root, int low, int high) { if (root == null) return 0; // 当前节点值太大，在左子树查找 if (root.val > high) return rangeSumBST(root.left, low, high); // 当前节点值太小，在右子树查找 if (root.val < low) return rangeSumBST(root.right, low, high); // 当前节点值在查找范围内 [low, high] return root.val + rangeSumBST(root.left, low, high) + rangeSumBST(root.right, low, high); } ``` ## 翻转等价二叉树（951） ### 递归 ```java public boolean flipEquiv(TreeNode root1, TreeNode root2) { // root1 和 root2 指向同一棵二叉树 或 都为 null。返回 true; if (root1 == root2) return true; // root1 和 root2 仅有一个为 null，或 它们的值不相等。返回 false if (root1 == null || root2 == null || root1.val != root2.val) return false; return (flipEquiv(root1.left, root2.left) && flipEquiv(root1.left, root2.right)) && (flipEquiv(root1.right, root2.right) || flipEquiv(root1.right, root2.left)); } ``` ### 标准态遍历 ```java public boolean flipEquiv(TreeNode root1, TreeNode root2) { List list1 = new ArrayList<>(); List list2 = new ArrayList<>(); dfs(root1, list1); dfs(root2, list2); return list1.equals(list2); } private void dfs(TreeNode node, List list) { if (node == null) return; list.add(node.val); int lVal = node.left == null ? -1 : node.left.val; int rVal = node.right == null ? -1 : node.right.val; if (lVal <= rVal) { dfs(node.left, list); dfs(node.right, list); } else { dfs(node.right, list); dfs(node.left, list); } // 不同深度的树可能会有相同的前序遍历，例如：[1,2,3] 和 [1,2,null,3] list.add(null); } ``` ## 二叉树的完全性检验（958） ```java public boolean isCompleteTree(TreeNode root) { List allNodes = new ArrayList<>(); allNodes.add(new ANode(root, 1)); // 层序遍历节点的指针 int i = 0; while (i < allNodes.size()) { ANode aNode = allNodes.get(i++); if (aNode.node != null) { allNodes.add(new ANode(aNode.node.left, aNode.num * 2)); allNodes.add(new ANode(aNode.node.right, aNode.num * 2 + 1)); } } return allNodes.get(i - 1).num == allNodes.size(); } private class ANode { private TreeNode node; private int num; private ANode(TreeNode node, int num) { this.node = node; this.num = num; } } ``` ## 单值二叉树（965） ```java public boolean isUnivalTree(TreeNode root) { if (root.left != null) { if (root.val != root.left.val || !isUnivalTree(root.left)) { return false; } } if (root.right != null) { if (root.val != root.right.val || !isUnivalTree(root.right)) { return false; } } return true; } ``` ## 监控二叉树（968） 本题的难点是 - 确认遍历方式 - 尽量在叶子节点的父节点上安装摄像头，这样才能保证安装的摄像头数量是最少的。所以，我们采用从下到上的方式去遍历二叉树 - 节点状态推导，确认了遍历方式后，我们可以通过下面三种基本状态进行推导 1. 当前节点没有被监控覆盖，但所有子节点都被监控覆盖了 2. 当前节点和所有子节点都被监控覆盖了，但当前节点没有摄像头 3. 当前节点和所有子节点都被监控覆盖了，并且当前节点有摄像头 `叶子节点相当于第二种状态` ```java public int minCameraCover(TreeNode root) { int[] ans = solve(root); return Math.min(ans[1], ans[2]); } /** * 该方法会返回如下三种情况，所需的最小摄像头数量 * 0: 当前节点没有被监控覆盖，但所有子节点都被监控覆盖了 * 1: 当前节点和所有子节点都被监控覆盖了，但当前节点没有摄像头 * 2: 当前节点和所有子节点都被监控覆盖了，并且当前节点有摄像头 * @param node * @return */ public int[] solve(TreeNode node) { if (node == null) return new int[]{0, 0, 99999}; int[] L = solve(node.left); int[] R = solve(node.right); int mL12 = Math.min(L[1], L[2]); int mR12 = Math.min(R[1], R[2]); // 如果 node 节点是 情况 0，左右子树必须是情况 1 int d0 = L[1] + R[1]; // 如果 node 节点是 情况 1，左右子树可以是 情况 1 或 情况 2，并且，必须有一棵子树是 情况 2 int d1 = Math.min(L[2] + mR12, R[2] + mL12); // 如果 node 节点是 情况 2，左右子树可以是 任何情况 int d2 = 1 + Math.min(L[0], mL12) + Math.min(R[0], mR12); return new int[]{d0, d1, d2}; } ``` ## 翻转二叉树以匹配先序遍历（971） ```java private int index = 0; public List flipMatchVoyage(TreeNode root, int[] voyage) { List path = new ArrayList<>(); flipMatchVoyage(root, voyage, path); return path; } private void flipMatchVoyage(TreeNode node, int[] voyage, List path) { if (node == null || (!path.isEmpty() && path.get(0) == -1)) return; if (node.val != voyage[index++]) { path.clear(); path.add(-1); return; } if (index < voyage.length && node.left != null && node.left.val != voyage[index]) { path.add(node.val); flipMatchVoyage(node.right, voyage, path); flipMatchVoyage(node.left, voyage, path); } else { flipMatchVoyage(node.left, voyage, path); flipMatchVoyage(node.right, voyage, path); } } ``` ## 在二叉树中分配硬币（979） ```java private int moves = 0; public int distributeCoins(TreeNode root) { dfs(root); return moves; } /** * dfs(node) 表示：当前节点 node 需要从父节点获取多少金币，才能让以 node 为根节点的子树满足每个节点均只有一枚金币。会有下面 3 种情况 * dfs(node) > 0 表示：需要向 node 的父节点移动 dfs(node) 枚金币 * dfs(node) = 0 表示：node 节点 与 父节点 之间不需要移动金币 * dfs(node) < 0 表示：node 的父节点需要向 node 节点移动 |dfs(node)| 枚金币 * * @param node * @return */ private int dfs(TreeNode node) { if (node == null) return 0; // 计算左右子树可交换次数 int leftCoins = dfs(node.left); int rightCoins = dfs(node.right); // 累加总共交换次数 moves += Math.abs(leftCoins) + Math.abs(rightCoins); // (当前节点数量 - 自己保留一个) + 左子节点交换数量 + 右子节点交换数量 return (node.val - 1) + leftCoins + rightCoins; } ``` ## 二叉树的垂序遍历（987） ```java public List> verticalTraversal(TreeNode root) { List nodes = new ArrayList<>(); // 将节点按 列, 行, 元素值 组成三元组 dfs(root, 0, 0, nodes); // 对 nodes 进行排序 Collections.sort(nodes, (aNode1, aNode2) -> { if (aNode1.col != aNode2.col) { // 比较列值 return aNode1.col - aNode2.col; } else if (aNode1.row != aNode2.row) { // 比较行值 return aNode1.row - aNode2.row; } else { // 比较元素值 return aNode1.val - aNode2.val; } }); List> ans = new ArrayList<>(); int index = -1; // 缓存上一列 int lastcol = Integer.MIN_VALUE; // 迭代 三元组，将相同的列放入一个数组中 for (ANode aNode : nodes) { int col = aNode.col, value = aNode.val; // 如果列值不同，创建新数组 if (col != lastcol) { lastcol = col; ans.add(new ArrayList<>()); index++; } // 获取最后一个数组 ans.get(index).add(value); } return ans; } private void dfs(TreeNode node, int row, int col, List nodes) { if (node == null) return; nodes.add(new ANode(row, col, node.val)); dfs(node.left, row + 1, col - 1, nodes); dfs(node.right, row + 1, col + 1, nodes); } private class ANode { private int row; private int col; private int val; private ANode(int row, int col, int val) { this.row = row; this.col = col; this.val = val; } } ``` ## 从叶结点开始的最小字符串（988） ```java public String smallestFromLeaf(TreeNode root) { // 记录最小的 node 集合 List minHightList = new ArrayList<>(); // 记录父子节点关系。key 子节点，val 父节点 Map parentMap = new HashMap<>(); Queue queue = new LinkedList<>(); queue.offer(root); int minVal = 26; while (!queue.isEmpty()) { int size = queue.size(); TreeNode node; for (int i = 0; i < size; i++) { node = queue.poll(); // 将值最小的叶子节点放入 minHightList 中 if (node.left == null && node.right == null) { if (node.val == minVal) { minHightList.add(node); } else if (node.val < minVal) { minVal = node.val; minHightList.clear(); minHightList.add(node); } } else { // 层序遍历的同时记录父子节点关系 if (node.left != null) { parentMap.put(node.left, node); queue.offer(node.left); } if (node.right != null) { parentMap.put(node.right, node); queue.offer(node.right); } } } } String ans = ""; for (TreeNode node : minHightList) { String str = buildString(node, parentMap); if (ans.isEmpty()) { ans = str; } else { if (ans.compareTo(str) > 0) { ans = str; } } } return ans; } private String buildString(TreeNode node, Map parentMap) { StringBuilder sb = new StringBuilder(); sb.append((char)(node.val + 97)); while (parentMap.containsKey(node)) { node = parentMap.get(node); sb.append((char)(node.val + 97)); } return sb.toString(); } ``` ## 二叉树的堂兄弟节点（993） ```java private int xHeight; private TreeNode xParent; private int yHeight; private TreeNode yParent; public boolean isCousins(TreeNode root, int x, int y) { dfs(null, root, x, y, 0); return xHeight == yHeight && xParent != yParent; } private void dfs(TreeNode parent, TreeNode node, int x, int y, int height) { if (node == null || (xParent != null && yParent != null)) return; if (node.val == x) { xHeight = height; xParent = parent; } else if (node.val == y) { yHeight = height; yParent = parent; } dfs(node, node.left, x, y, height + 1); dfs(node, node.right, x, y, height + 1); } ``` ## 最大二叉树 II（998） ```java public TreeNode insertIntoMaxTree(TreeNode root, int val) { TreeNode parent = null; TreeNode cur = root; while (cur != null) { // 找到待插入的位置 if (cur.val < val) { if (parent == null) { // 1. 插入根节点 return new TreeNode(val, root, null); } else { // 2. 插入其他节点 TreeNode node = new TreeNode(val, cur, null); parent.right = node; return root; } } else { // 继续向右迭代。 // 由于新插入节点在数组的末尾，当 cur.val > val 时，新节点一定是 cur 的右子树 parent = cur; cur = cur.right; } } // 3. 走到这里表示，一直向右遍历，都没有找到插入点 parent.right = new TreeNode(val); return root; } ``` ## 前序遍历构造二叉搜索树（1008） ```java public TreeNode bstFromPreorder(int[] preorder) { return buildTree(preorder, 0, preorder.length -1); } private TreeNode buildTree(int[] preorder, int start, int end) { if (start > end) return null; if (start == end) return new TreeNode(preorder[start]); TreeNode root = new TreeNode(preorder[start]); int l = start; int r = end; // 查找 最后一个比 preorder[start] 小的下标 while (l < r) { // 由于 mid 不 +1，这里要 +1 int mid = (r - l + 1) / 2 + l; if (preorder[mid] < preorder[start]) { // 由于要找比目标值小的最后一个索引，所以 mid 不 +1 l = mid; } else { // 由于要找比目标值小的最后一个索引，所以 mid 可以 -1 r = mid - 1; } } root.left = buildTree(preorder, start + 1, l); root.right = buildTree(preorder, l + 1, end); return root; } ``` ## 从根到叶的二进制数之和（1022） ```java public int sumRootToLeaf(TreeNode root) { return dfs(root, 0); } /** * 根据 父节点的值 求当前节点的累加值 * @param node * @param val 父节点值 */ private int dfs(TreeNode node, int val) { // 空节点不参与计算 if (node == null) return 0; // 将当前节点的值与父节点拼接 val = val << 1 | node.val; // 如果是叶子节点直接返回 val if (node.left == null && node.right == null) return val; // 走到这里表示，node 不是叶子节点 // 返回左右子树的累加和 return dfs(node.left, val) + dfs(node.right, val); } ``` ## 节点与其祖先之间的最大差值（1026） ```java public int maxAncestorDiff(TreeNode root) { return dfs(root, root.val, root.val); } private int dfs(TreeNode node, int min, int max) { // 空节点不参与计算，返回最大差值为 0 if (node == null) return 0; int diff = Math.max(Math.abs(node.val - min), Math.abs(node.val - max)); min = Math.min(min, node.val); max = Math.max(max, node.val); diff = Math.max(diff, dfs(node.left, min, max)); diff = Math.max(diff, dfs(node.right, min, max)); return diff; } ``` ## 从先序遍历还原二叉树（1028） ```java public TreeNode recoverFromPreorder(String traversal) { Deque stack = new LinkedList<>(); int pos = 0; while (pos < traversal.length()) { int level = 0; // 获取当前节点的 深度 while (traversal.charAt(pos) == '-') { ++level; ++pos; } // 获取当前节点值 int value = 0; while (pos < traversal.length() && Character.isDigit(traversal.charAt(pos))) { value = value * 10 + (traversal.charAt(pos) - '0'); ++pos; }！ // 构建当前节点 TreeNode node = new TreeNode(value); // 如果当前节点深度 = 前继节点深度 + 1 if (level == stack.size()) { // 有前继节点 if (!stack.isEmpty()) { // 当前节点就是前继节点的左子节点 stack.peek().left = node; } } else { // 在 栈中寻找前继节点 while (level != stack.size()) { stack.pop(); } // 当前节点就是该节点的右子节点 stack.peek().right = node; } stack.push(node); } return stack.pollLast(); } ``` ## 从二叉搜索树到更大和树（1038） ```java int sum = 0; public TreeNode bstToGst(TreeNode root) { if (root != null) { bstToGst(root.right); sum += root.val; root.val = sum; bstToGst(root.left); } return root; } ``` ## 根到叶路径上的不足节点（1080） ```java public TreeNode sufficientSubset(TreeNode root, int limit) { boolean b = dfs(root, 0, limit); return b ? root : null; } /** * 从当前节点出发，所有子树是否能找到不是 不足点 的路径 * @param node * @param sum 父节点路径和 * @param limit 要求值 * @return */ private boolean dfs(TreeNode node, int sum, int limit) { if (node == null) return false; if (node.left == null && node.right == null) return node.val + sum >= limit; boolean l = dfs(node.left, sum + node.val, limit); boolean r = dfs(node.right, sum + node.val, limit); if (!l) node.left = null; if (!r) node.right = null; return l || r; } ``` ## 二叉树寻路（1104） ```java public List pathInZigZagTree(int label) { // 获取给定值的二进制表示 String binaryString = Integer.toBinaryString(label); int len = binaryString.length(); // 如果二进制表示的长度为 偶数 表示需要转换 if (len % 2 == 0) { // (1 << (len - 1)) 表示当前行最小值 // ((1 << len) - 1) 表示当前行最大值 // label 表示当前值 label = (1 << (len - 1)) + ((1 << len) - 1) - label; binaryString = Integer.toBinaryString(label); } // 根据二进制字符串，获取路径 List retList = new ArrayList<>(); int val = 0; for (int i = 0; i < binaryString.length(); i++) { // 获取当前值 val = (val << 1) + (binaryString.charAt(i) - '0'); // 根据 i 值判断是否需要转换结果 if (i % 2 == 1) { // (1 << i) 表示当前行最小值 // ((1 << (i + 1)) - 1) 表示当前行最大值 retList.add((1 << i) + ((1 << (i + 1)) - 1) - val); } else { retList.add(val); } } return retList; } ``` ## 删点成林（1110） ```java public List delNodes(TreeNode root, int[] to_delete) { Set delSet = new HashSet(); for (int val : to_delete) { delSet.add(val); } List roots = new ArrayList(); dfs(root, true, delSet, roots); return roots; } /** * * @param node * @param isRoot 当前节点 node 是否为根节点 * @param delSet * @param roots * @return */ public TreeNode dfs(TreeNode node, boolean isRoot, Set delSet, List roots) { if (node == null) return null; // 当前节点是否应该被删除 boolean deleted = delSet.contains(node.val); // 如果当前节点被删除，其子节点就可作为根节点 node.left = dfs(node.left, deleted, delSet, roots); node.right = dfs(node.right, deleted, delSet, roots); if (deleted) { // 如果当前节点应被删除，返回 null。表示，将 null 挂到父节点下 return null; } else { if (isRoot) { roots.add(node); } return node; } } ``` ## 最深叶节点的最近公共祖先（1123） ```java public TreeNode lcaDeepestLeaves(TreeNode root) { return dfs(root).getKey(); } /** * 获取 lca 和 最大深度 * @param root * @return */ private Pair dfs(TreeNode root) { // 空节点不参与比较，直接返回 null，深度 0 if (root == null) { return new Pair<>(root, 0); } // 获取左右子树的 lca 和 最大深度 Pair left = dfs(root.left); Pair right = dfs(root.right); // 左子树更深 if (left.getValue() > right.getValue()) { return new Pair<>(left.getKey(), left.getValue() + 1); } // 右子树更深 if (left.getValue() < right.getValue()) { return new Pair<>(right.getKey(), right.getValue() + 1); } // 左右子树深度相同 return new Pair<>(root, left.getValue() + 1); } ``` ## 二叉树着色游戏（1145） ```java public boolean btreeGameWinningMove(TreeNode root, int n, int x) { // 寻找 x 节点 TreeNode node = find(root, x); // 获取左子树节点数 int leftSize = getSubtreeSize(node.left); // 判断节点数是否过半 if (leftSize >= (n + 1) / 2) { return true; } // 获取右子树节点数 int rightSize = getSubtreeSize(node.right); // 判断节点数是否过半 if (rightSize >= (n + 1) / 2) { return true; } // 获取剩余节点数 int remain = n - 1 - leftSize - rightSize; // 判断是否过半 return remain >= (n + 1) / 2; } public TreeNode find(TreeNode node, int x) { if (node == null) return null; if (node.val == x) return node; TreeNode l = find(node.left, x); if (l != null) return l; TreeNode r = find(node.right, x); if (r != null) return r; return null; } public int getSubtreeSize(TreeNode node) { if (node == null) return 0; return 1 + getSubtreeSize(node.left) + getSubtreeSize(node.right); } ``` ## 最大层内元素和（1161） ```java public int maxLevelSum(TreeNode root) { Queue queue = new LinkedList<>(); queue.offer(root); int sum = Integer.MIN_VALUE; int ans = 1; int level = 1; while (!queue.isEmpty()) { int size = queue.size(); int curSum = 0; for(int i = 0; i< size; i++) { TreeNode node = queue.poll(); curSum += node.val; if (node.left != null) queue.offer(node.left); if (node.right != null) queue.offer(node.right); } if (sum < curSum) { sum = curSum; ans = level; } level++; } return ans; } ``` ## 在受污染的二叉树中查找元素（1261） ```java private TreeNode root; public _1261_在受污染的二叉树中查找元素_dfs_位运算(TreeNode root) { dfs(root, 0); this.root = root; } private void dfs(TreeNode node, int val) { node.val = val; if (node.left != null) dfs(node.left, 2 * val + 1); if (node.right != null) dfs(node.right, 2 * val + 2); } public boolean find(int target) { target++; // 这里是 30 而不是 32 是因为，从 0 位开始计数(减1)，最左边的那一位不计入(又减1)。 int k = 30 - Integer.numberOfLeadingZeros(target); TreeNode node = this.root; while (k >= 0 && node != null) { if ((target & (1 << k)) == 0) { node = node.left; } else { node = node.right; } k--; } return node != null; } ``` ## 层数最深叶子节点的和（1302） ```java public int deepestLeavesSum(TreeNode root) { List q = new ArrayList<>(); q.add(root); while (true) { int sum = 0; List nq = new ArrayList<>(); for (TreeNode node : q) { sum += node.val; if (node.left != null) nq.add(node.left); if (node.right != null) nq.add(node.right); } q = nq; if (q.isEmpty()) return sum; } } ``` ## 两棵二叉搜索树中的所有元素（1305） ```java public List getAllElements(TreeNode root1, TreeNode root2) { List list1 = new ArrayList<>(); List list2 = new ArrayList<>(); inorder(root1, list1); inorder(root2, list2); List retList = new ArrayList<>(); int i1 = 0, i2 = 0; int len1 = list1.size(), len2 = list2.size(); while (i1 < len1 && i2 < len2) { if (list1.get(i1) <= list2.get(i2)) { retList.add(list1.get(i1++)); } else { retList.add(list2.get(i2++)); } } if (i1 < len1) { while (i1 < len1) { retList.add(list1.get(i1++)); } } else { while (i2 < len2) { retList.add(list2.get(i2++)); } } return retList; } public void inorder(TreeNode node, List list) { if (node == null) return; inorder(node.left, list); list.add(node.val); inorder(node.right, list); } ``` ## 祖父节点值为偶数的节点和（1315） ```java private int sum; public int sumEvenGrandparent(TreeNode root) { dfs(root, false, false); return sum; } /** * * @param node * @param grandParent 祖父节点是否为偶数节点 * @param parent 父节点是否为偶数节点 */ private void dfs(TreeNode node, boolean grandParent, boolean parent) { if (node == null) return; if (grandParent) sum += node.val; dfs(node.left, parent, node.val % 2 == 0); dfs(node.right, parent, node.val % 2 == 0); } ``` ## 删除给定值的叶子节点（1325） ```java public TreeNode removeLeafNodes(TreeNode root, int target) { if (root == null) return null; root.left = removeLeafNodes(root.left, target); root.right = removeLeafNodes(root.right, target); if (root.left == null && root.right == null && root.val == target) return null; return root; } ``` ## 分裂二叉树的最大乘积（1339） ```java // 树中所有节点值之和 private int sum = 0; // 删除一条边后，对应的子节点会成为新树的根节点 // 存储的就是新树的节点值之和（它最终会存储最接近 sum / 2 的那个值） private int sum_n = 0; public int maxProduct(TreeNode root) { sum(root); dfs(root); return (int)(((long) sum_n * (sum - sum_n)) % 1000000007); } // 求所有节点和 private void sum(TreeNode node) { if (node == null) return; sum += node.val; sum(node.left); sum(node.right); } /** * 求以给定节点为根节点的树中所有节点值之和 * @param node * @return */ private int dfs(TreeNode node) { if (node == null) return 0; int l = dfs(node.left); int r = dfs(node.right); int cur = l + r + node.val; // 根据 均值不等式，当 sum 为一个固定值，sum_n 越接近 sum / 2，sum_n * （sum - sum_n） 的值越大 if (Math.abs(cur * 2 - sum) < Math.abs(sum_n * 2 - sum)) { sum_n = cur; } return cur; } ``` ## 验证二叉树（1361） ```java public boolean validateBinaryTreeNodes(int n, int[] leftChild, int[] rightChild) { // 计算所有节点的 入度 int[] indeg = new int[n]; for (int i = 0; i < n; i++) { if (leftChild[i] != -1) { indeg[leftChild[i]] += 1; } if (rightChild[i] != -1) { indeg[rightChild[i]] += 1; } } // 寻找根节点 int root = -1; for (int i = 0; i < n; i++) { if (indeg[i] == 0) { root = i; break; } } // 所有节点 入度 都不为 0 if (root == -1) return false; Set visited = new HashSet<>(); Queue queue = new LinkedList<>(); queue.offer(root); visited.add(root); while (!queue.isEmpty()) { // 获取当前节点编号 int num = queue.poll(); // 当前节点的左子节点不为空 if (leftChild[num] != -1) { // 左子节点已被访问过，返回 false if (visited.contains(leftChild[num])) return false; visited.add(leftChild[num]); queue.offer(leftChild[num]); } // 当前节点的右子节点不为空 if (rightChild[num] != -1) { // 右子节点已被访问过，返回 false if (visited.contains(rightChild[num])) return false; visited.add(rightChild[num]); queue.offer(rightChild[num]); } } return visited.size() == n; } ``` ## 二叉树中的链表（1367） ```java public boolean isSubPath(ListNode head, TreeNode root) { if (root == null) return false; return dfs(head, root) || isSubPath(head, root.left) || isSubPath(head, root.right); } // 从二叉树的给定节点出发，一直向下找，是否与链表匹配 private boolean dfs(ListNode head, TreeNode node) { // 匹配到链表尾部，匹配成功 if (head == null) return true; // 匹配到二叉树的空节点，匹配失败 if (node == null) return false; // 值不相等，匹配失败 if (head.val != node.val) return false; return dfs(head.next, node.left) || dfs(head.next, node.right); } ``` ## 二叉树中的最长交错路径（1372） ```java private int ans = 0; public int longestZigZag(TreeNode root) { if (root == null) return 0; // 应该向左子节点移动 dfs(root, false, 0); // 应该向右子节点移动 dfs(root, true, 0); return ans; } /** * 已 node 为起始节点，向 node 节点的 dir 方向移动，当前交错路径长度为 len * @param node * @param dir true 向 node 节点的右子节点移动，false 向 node 节点的左子节点移动 * @param len */ private void dfs(TreeNode node, boolean dir, int len) { ans = Math.max(ans, len); if (dir) { // 应该向右子节点移动 if (node.right != null) { // 下次就应该左子节点移动了，步长 + 1 dfs(node.right, false, len + 1); } if (node.left != null) { // 重置步长，因为 node.left 一定有父节点，所以，步长是 1 dfs(node.left, true, 1); } } else { // 应该向左子节点移动 if (node.left != null) { dfs(node.left, true, len + 1); } if (node.right != null) { dfs(node.right, false, 1); } } } ``` ## 二叉搜索子树的最大键值和（1373） ```java private int res = 0; class NodeInfo { // 以当前节点为根的树，是否为二叉搜索树 private boolean isBST; // 以当前节点为根的树中，节点的最小值 private int minValue; // 以当前节点为根的树中，节点的最大值 private int maxValue; // 以当前节点为根的树中，节点值之和 private int sumValue; private NodeInfo(boolean isBST, int minValue, int maxValue, int sumValue) { this.isBST = isBST; this.minValue = minValue; this.maxValue = maxValue; this.sumValue = sumValue; } } public int maxSumBST(TreeNode root) { dfs(root); return res; } public NodeInfo dfs(TreeNode root) { // 空节点不影响计算结果 if (root == null) return new NodeInfo(true, Integer.MAX_VALUE, Integer.MIN_VALUE, 0); NodeInfo left = dfs(root.left); NodeInfo right = dfs(root.right); if (left.isBST && right.isBST && root.val > left.maxValue && root.val < right.minValue) { // 以当前节点为根的树，也是二叉搜索树 // 更新结果 int sum = root.val + left.sumValue + right.sumValue; res = Math.max(res, sum); return new NodeInfo(true, Math.min(left.minValue, root.val), Math.max(root.val, right.maxValue), sum); } else { // 当前节点不是二叉搜索树，minValue，maxValue，sumValue 的值随便填，不会影响结果（因为不会进入上面的 if，所以不参与结果计算） return new NodeInfo(false, 0, 0, 0); } } ``` ## 找出克隆二叉树中的相同节点（1379） ```java public final TreeNode getTargetCopy(final TreeNode original, final TreeNode cloned, final TreeNode target) { if (original == null) return null; if (original == target) return cloned; TreeNode node = getTargetCopy(original.left, cloned.left, target); if (node != null) return node; return getTargetCopy(original.right, cloned.right, target); } ``` ## 将二叉搜索树变平衡（1382） ```java private List inorderList = new ArrayList(); public TreeNode balanceBST(TreeNode root) { // 1. 中序遍历二叉搜索树，并将结果放入 inorderList 中 getInorder(root); // 2. 通过 inorderList 重构二叉搜索树 return build(0, inorderList.size() - 1); } private void getInorder(TreeNode node) { if (node == null) return; getInorder(node.left); inorderList.add(node.val); getInorder(node.right); } /** * 对区间 [l, r] 构建树 * @param l 中序遍历索引 * @param r 中序遍历索引 * @return */ private TreeNode build(int l, int r) { int mid = ((r - l) >> 1) + l; TreeNode root = new TreeNode(inorderList.get(mid)); if (l <= mid - 1) { root.left = build(l, mid - 1); } if (r >= mid + 1) { root.right = build(mid + 1, r); } return root; } ``` ## 统计二叉树中好节点的数目（1448） ```java private int ans = 0; public int goodNodes(TreeNode root) { dfs(root, root.val); return ans; } private void dfs(TreeNode node, int maxVal) { if (node == null) return; if (node.val >= maxVal) { ans++; maxVal = node.val; } dfs(node.left, maxVal); dfs(node.right, maxVal); } ``` ## 二叉树中的伪回文路径（1457） ```java public int pseudoPalindromicPaths (TreeNode root) { int[] counter = new int[10]; return dfs(root, counter); } /** * 求根节点到以该节点为祖先的叶子节点的所有路径中伪回文路径的数目 * @param node * @param counter 记录路径中各个值出现的次数 * @return */ private int dfs(TreeNode node, int[] counter) { if (node == null) return 0; ++counter[node.val]; int ans = 0; if (node.left == null && node.right == null) { int odd = 0; for (int i : counter) { if (i % 2 == 1) { odd++; } } if (odd <= 1) { ans++; } } else { ans = dfs(node.left, counter) + dfs(node.right, counter); } --counter[node.val]; return ans; } ``` ## 好叶子节点对的数量（1530） ```java public int countPairs(TreeNode root, int distance) { Pair pair = dfs(root, distance); return pair.count; } // 对于 dfs(root,distance)，同时返回： // 1）每个叶子节点与 root 之间的距离 // 2) 以 node 为根节点的子树中好叶子节点对的数量 public Pair dfs(TreeNode node, int distance) { // depths[i] 表示，离 node 节点距离为 i 的 叶子节点的个数 int[] depths = new int[distance + 1]; boolean isLeaf = node.left == null && node.right == null; if (isLeaf) { // node 是叶子节点，自己和自己的距离为 0 depths[0] = 1; return new Pair(depths, 0); } // leftDepths[i] 表示离 node.left 节点距离为 i 的 叶子节点的个数 // rightDepths[j] 表示离 node.right 节点距离为 j 的 叶子节点的个数 int[] leftDepths = new int[distance + 1]; int[] rightDepths = new int[distance + 1]; // 以 node.left 或 node.right 为根节点的子树中好叶子节点对的数量 int leftCount = 0, rightCount = 0; if (node.left != null) { Pair leftPair = dfs(node.left, distance); leftDepths = leftPair.depths; leftCount = leftPair.count; } if (node.right != null) { Pair rightPair = dfs(node.right, distance); rightDepths = rightPair.depths; rightCount = rightPair.count; } // leftDepths 中的叶子节点离 node.left 的距离是 i，那么离 node 就是 i + 1 // rightDepths 中的叶子节点离 node.right 的距离是 i，那么离 node 就是 i + 1 for (int i = 0; i < distance; i++) { depths[i + 1] += leftDepths[i]; depths[i + 1] += rightDepths[i]; } // 必须经过 node 节点，有多少好叶子节点 int cnt = 0; // 求距离左子节点为 i，右子节点为 j 的叶子节点有多少对，（i + 1 + j + 1 <= distance，这些是符合要求的叶子节点） for (int i = 0; i <= distance; i++) { // j + i + 2 可拆分为 j + 1 + i + 1 表示离 node 的距离为 j + 1 和 i + 1 的 叶子节点的个数 for (int j = 0; j + i + 2 <= distance; j++) { // 相乘是因为排列组合，例如：leftDepths[i] = 2, rightDepths[j] = 3, 则一共可以有 6 个叶子节点对 cnt += leftDepths[i] * rightDepths[j]; } } return new Pair(depths, cnt + leftCount + rightCount); } class Pair { // depths[i] 表示，离 node 节点距离为 i 的 叶子节点的个数 int[] depths; // 以 node 为根节点的子树中好叶子节点对的数量 int count; public Pair(int[] depths, int count) { this.depths = depths; this.count = count; } } ``` ## 将子数组重新排序得到同一个二叉搜索树的方案数（1569） ```java private final int MOD = 1_000_000_007; // c[i][j] 表示，从 i 中选择 j 个 private long[][] c; public int numOfWays(int[] nums) { int n = nums.length; if (n == 1) return 0; // 预计算 从 i 中选择 j 个 c = new long[n][n]; c[0][0] = 1; for (int i = 1; i < n; ++i) { c[i][0] = 1; for (int j = 1; j < n; ++j) { c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % MOD; } } // 以 第一个元素为根节点，依次将数组中的元素插入到二叉查找树中 TreeNode root = new TreeNode(nums[0]); for (int i = 1; i < n; ++i) { int val = nums[i]; insert(root, val); } dfs(root); // + MOD 是因为当 root.ans 为 MOD 的整数倍时，root.ans 为 0。0 - 1 变成了 -1，所以要 + MOD return (root.ans - 1 + MOD) % MOD; } private void insert(TreeNode node, int value) { while (true) { ++node.size; if (value < node.value) { if (node.left == null) { node.left = new TreeNode(value); return; } node = node.left; } else { if (node.right == null) { node.right = new TreeNode(value); return; } node = node.right; } } } private void dfs(TreeNode node) { if (node == null) return; dfs(node.left); dfs(node.right); // 左子树元素个数 int lsize = node.left != null ? node.left.size : 0; // 右子树元素个数 int rsize = node.right != null ? node.right.size : 0; // 左子树相同排列方案 int lans = node.left != null ? node.left.ans : 1; // 右子树相同排列方案 int rans = node.right != null ? node.right.ans : 1; // 去掉根节点，从 剩余的位置选择 左子树放置的位置 * 在这些位置中，左子树的排列方案 * 在剩余位置中，右子树排列方案 node.ans = (int) (c[lsize + rsize][lsize] % MOD * lans % MOD * rans % MOD); } private class TreeNode { private TreeNode left; private TreeNode right; private int value; // 当前二叉搜索树中的元素个数 private int size; // 可以构成相同二叉搜索树的排列方案数 private int ans; private TreeNode(int value) { this.value = value; this.size = 1; this.ans = 0; } } ``` ## 奇偶树（1609） ```java public boolean isEvenOddTree(TreeNode root) { Queue queue = new LinkedList<>(); queue.offer(root); int level = 0; while (!queue.isEmpty()) { int preVal = level % 2 == 0 ? Integer.MIN_VALUE : Integer.MAX_VALUE; int size = queue.size(); for (int i = 0; i < size; i++) { TreeNode node = queue.poll(); // 偶数层出现偶数 || 奇数层出现奇数 都返回 false if (node.val % 2 == level % 2) return false; // 偶数层没有严格递增 || 奇数层没有严格递减 都返回 false if ((level % 2 == 0 && preVal >= node.val) || (level % 2 == 1 && preVal <= node.val)) return false; if (node.left != null) queue.offer(node.left); if (node.right != null) queue.offer(node.right); preVal = node.val; } level++; } return true; } ``` ## 合并多棵二叉搜索树（1932） ```java // 存储所有叶节点值的哈希集合 HashSet leaves = new HashSet<>(); // 存储 (根节点值, 树) 键值对的哈希映射 HashMap candidates = new HashMap<>(); // 存储中序遍历上一个遍历到的值，便于检查严格单调性 int prev = 0; public TreeNode canMerge(List trees) { // 构造 leaves 和 candidates for (TreeNode tree : trees) { if (tree.left != null) leaves.add(tree.left.val); if (tree.right != null) leaves.add(tree.right.val); candidates.put(tree.val, tree); } for (TreeNode tree : trees) { // 不包含在 leaves 中的根节点，才是合并后的树根 if (!leaves.contains(tree.val)) { // 将其从哈希映射中移除 candidates.remove(tree.val); // 从根节点开始进行遍历 // 如果中序遍历有严格单调性，并且所有树的根节点都被遍历到，说明可以构造二叉搜索树 prev = 0; return (dfs(tree) && candidates.isEmpty()) ? tree : null; } } return null; } // 构建树，并中序遍历，返回值表示是否有严格单调性 private boolean dfs(TreeNode node) { if (node == null) return true; // 如果遍历到叶节点，并且存在可以合并的树，那么就进行合并 if (node.left == null && node.right == null && candidates.containsKey(node.val)) { node.left = candidates.get(node.val).left; node.right = candidates.get(node.val).right; // 合并完成后，将树从哈希映射中移除，以便于在遍历结束后判断是否所有树都被遍历过 candidates.remove(node.val); } // 先遍历左子树 if (!dfs(node.left)) { return false; } // 再遍历当前节点 if (node.val <= prev) { return false; } prev = node.val; // 最后遍历右子树 return dfs(node.right); } ``` ## 统计最高分的节点数目（2049） ```java // 最高分数 private long maxScore = 0; // 最高分数的节点共有多少个 private int cnt = 0; // 原树节点总数 private int total; // List[i] 表示，节点 i 的左右子节点存储在 List 中 private List[] children; public int countHighestScoreNodes(int[] parents) { total = parents.length; // 构造 children 数组 children = new List[total]; for (int i = 0; i < total; i++) { children[i] = new ArrayList<>(); } for (int i = 0; i < total; i++) { int p = parents[i]; if (p != -1) { children[p].add(i); } } dfs(0); return cnt; } // 返回值：以 node 为根节点的子树的节点个数 public int dfs(int node) { long score = 1; // remain = 树中节点总数 - 当前节点 - 左子树节点数目 - 右子树节点数目 // 当 node 为根节点时 remain = 0 // 不为根节点时，remain = 原树 删除以 node 为根的子树，剩余部分的节点数 int remain = total - 1; for (int c : children[node]) { int t = dfs(c); score *= t; remain -= t; } if (node != 0) { score *= remain; } if (score == maxScore) { cnt++; } else if (score > maxScore) { maxScore = score; cnt = 1; } // n - remain = 树中节点总数 - (树中节点总数 - 当前节点 - 左子树节点数目 - 右子树节点数目) // n - remain = 当前节点 + 左子树节点数目 + 右子树节点数目 // 所以 n - remain 表示，以 node 为根节点的子树的节点个数 return total - remain; } ``` ## 从二叉树一个节点到另一个节点每一步的方向(2096) ```java // key: childNode, val: parentNode private Map pMap = new HashMap<>(); // sNode: start node; dNode: dest node private TreeNode sNode, dNode; public String getDirections(TreeNode root, int startValue, int destValue) { dfs(root, startValue, destValue); String path1 = path(root, sNode); String path2 = path(root, dNode); // 计算最长公共前缀 并删去对应部分，同时将 path1 逐字符修改为 'U' int l1 = path1.length(); int l2 = path2.length(); int i = 0; while (i < Math.min(l1, l2)) { if (path1.charAt(i) == path2.charAt(i)) { i++; } else { break; } } StringBuilder ret = new StringBuilder(); int repeatCount = l1 - i; for (int j = 0; j < repeatCount; j++) { ret.append('U'); } ret.append(path2.substring(i)); return ret.toString(); } /** * 遍历树中所有节点，并初始化 pMap, sNode, dNode * @param node * @param startValue * @param destValue */ private void dfs(TreeNode node, int startValue, int destValue) { if (node.val == startValue) sNode = node; if (node.val == destValue) dNode = node; if (node.left != null) { pMap.put(node.left, node); dfs(node.left, startValue, destValue); } if (node.right != null) { pMap.put(node.right, node); dfs(node.right, startValue, destValue); } } /** * 返回从 root 节点到 node 节点的路径 * @param root * @param node * @return */ private String path(TreeNode root, TreeNode node) { StringBuilder sb = new StringBuilder(); // 从 node 节点向上查找，一直到 root 节点的路径 while (node != root) { TreeNode pNode = pMap.get(node); if (node == pNode.left) sb.append("L"); if (node == pNode.right) sb.append("R"); node = pNode; } // 将路径反转 return sb.reverse().toString(); } ``` ## 根据描述创建二叉树（2196） ```java public TreeNode createBinaryTree(int[][] descriptions) { // 存储所有非根节点 Set childSet = new HashSet<>(); // key: 节点值, val: TreeNode Map nodeMap = new HashMap<>(); for (int[] nodeInfo : descriptions) { int pVal = nodeInfo[0]; int cVal = nodeInfo[1]; int isLeft = nodeInfo[2]; if (!nodeMap.containsKey(pVal)) nodeMap.put(pVal, new TreeNode(pVal)); if (!nodeMap.containsKey(cVal)) nodeMap.put(cVal, new TreeNode(cVal)); if (isLeft == 1) { nodeMap.get(pVal).left = nodeMap.get(cVal); } else { nodeMap.get(pVal).right = nodeMap.get(cVal); } childSet.add(cVal); } for (Integer pVal : nodeMap.keySet()) { if (!childSet.contains(pVal)) { return nodeMap.get(pVal); } } return null; } ``` ## 判断根结点是否等于子结点之和（2236） ```java public boolean checkTree(TreeNode root) { return root.val == root.left.val + root.right.val; } ``` ## 统计值等于子树平均值的节点数（2265） ```java private int ans; public int averageOfSubtree(TreeNode root) { dfs(root); return ans; } /** * 返回以 node 为根 的子树 节点合 和 节点个数 * @param node * @return */ private int[] dfs(TreeNode node) { int sum = 0; int cnt = 0; if (node.left != null) { int[] l = dfs(node.left); sum += l[0]; cnt += l[1]; } if (node.right != null) { int[] r = dfs(node.right); sum += r[0]; cnt += r[1]; } sum += node.val; cnt += 1; if ((sum / cnt) == node.val) ans++; return new int[]{sum, cnt}; } ``` ## 计算布尔二叉树的值（2331） ```java public boolean evaluateTree(TreeNode root) { if (root.left == null) return root.val == 1; boolean l = evaluateTree(root.left); boolean r = evaluateTree(root.right); return root.val == 2 ? (l || r) : (l && r); } ``` ## 感染二叉树需要的总时间（2385） ```java public int amountOfTime(TreeNode root, int start) { // key: 节点值, val: 相邻节点 list Map> graph = new HashMap<>(); // 1. 深度优先搜索建图 dfs(graph, root); // 2. 广度优先搜索求感染时间 Queue queue = new ArrayDeque<>(); // int[0] 节点值；int[1] 感染时间 queue.offer(new int[]{start, 0}); // 已访问节点值 Set visited = new HashSet<>(); visited.add(start); int time = 0; while (!queue.isEmpty()) { int[] arr = queue.poll(); int nodeVal = arr[0]; time = arr[1]; for (int childVal : graph.get(nodeVal)) { if (visited.add(childVal)) { queue.offer(new int[]{childVal, time + 1}); } } } return time; } public void dfs(Map> graph, TreeNode node) { graph.putIfAbsent(node.val, new ArrayList<>()); for (TreeNode child : Arrays.asList(node.left, node.right)) { if (child == null) continue; graph.get(node.val).add(child.val); graph.putIfAbsent(child.val, new ArrayList<>()); graph.get(child.val).add(node.val); dfs(graph, child); } } ``` ## 反转二叉树的奇数层（2415） ```java public TreeNode reverseOddLevels(TreeNode root) { List list = new LinkedList<>(); list.add(root); int level = 0; while (!list.isEmpty()) { int size = list.size(); // 当是奇数层时，通过双指针进行反转 if (level % 2 == 1) { for (int i = 0, j = size - 1; i < j; i++, j--) { TreeNode l = list.get(i); TreeNode r = list.get(j); int tmp = l.val; l.val = r.val; r.val = tmp; } } List newList = new ArrayList<>(); for (int i = 0; i < size; i++) { TreeNode node = list.get(i); if (node.left != null) newList.add(node.left); if (node.right != null) newList.add(node.right); } level++; list = newList; } return root; } ``` ## 移除子树后的二叉树高度（2458） ```java // 每棵子树的高度，key：当前节点，value：已当前节点为根的子树高度 private Map height = new HashMap<>(); // 索引：表示指定节点值，值：指定节点被删除后，树的最大高度 private int[] res; public int[] treeQueries(TreeNode root, int[] queries) { // 1. 获取每个节点的高度 getHeight(root); // 简化 dfs 的代码，这样不用写 getOrDefault height.put(null, 0); res = new int[height.size()]; dfs(root, -1, 0); for (int i = 0; i < queries.length; i++) queries[i] = res[queries[i]]; return queries; } // 获取 以 node 为根的子树高度 private int getHeight(TreeNode node) { if (node == null) return 0; int h = 1 + Math.max(getHeight(node.left), getHeight(node.right)); height.put(node, h); return h; } /** * * @param node 当前节点 * @param depth + 1 当前节点深度 * @param restH 删除当前子树后，剩余部分的高度 */ private void dfs(TreeNode node, int depth, int restH) { if (node == null) return; ++depth; // 指定节点被删除后，树的最大高度 res[node.val] = restH; // 求左子树被删除后，树的最大高度 dfs(node.left, depth, Math.max(restH, depth + height.get(node.right))); // 求右子树被删除后，树的最大高度 dfs(node.right, depth, Math.max(restH, depth + height.get(node.left))); } ``` ## 逐层排序二叉树所需的最少操作数目（2471） ```java public int minimumOperations(TreeNode root) { int res = 0; // 树为 null 的情况 if (root == null) return res; Queue queue = new LinkedList<>(); queue.add(root); while (!queue.isEmpty()) { // 存储当前层所有节点值（无序） List levelList = new ArrayList<>(); int size = queue.size(); // 得到该层全部节点 for (int i = 0; i < size; i++) { TreeNode node = queue.poll(); levelList.add(node.val); if (node.left != null) queue.add(node.left); if (node.right != null) queue.add(node.right); } // 计算该层节点交换次数 // 统计环数 int loop = 0; // 存储当前层所有节点值（无序） List temp = new ArrayList<>(levelList); // 用于标记 temp[i] 是否已经被加入环中 boolean[] flag = new boolean[temp.size()]; // 此时 levelList 已经有序 Collections.sort(levelList); // key: 节点值, val: 排序后所在下标 HashMap map = new HashMap<>(); for (int i = 0; i < levelList.size(); i++) { map.put(levelList.get(i), i); } // 计算有多少个环 for (int i = 0; i < temp.size(); i++) { if (!flag[i]) { // 环起始位置 int j = i; // 绘制环 while (!flag[j]) { // temp.get(j) 表示，获取当前节点值 // map.get(当前节点值) 表示，获取当前节点值排序后所在下标 // 因此，index 就相当于环上下一个节点所在位置 int index = map.get(temp.get(j)); // 将 j 加入环中 flag[j] = true; // 将当前节点索引移动到环上下个节点 j = index; } loop++; } } // 当前层最小交互次数 节点个数 - 环数 res += (temp.size() - loop); } return res; } ``` ## 二叉搜索树最近节点查询（2476） ```java public List> closestNodes(TreeNode root, List queries) { // 1. 中序遍历 二叉树，将结果存入 arr List arr = new ArrayList<>(); dfs(root, arr); List> res = new ArrayList<>(); for (int val : queries) { int maxVal = -1, minVal = -1; int idx = binarySearch(arr, val); if (idx != arr.size()) { maxVal = arr.get(idx); if (arr.get(idx) == val) { minVal = val; List list = new ArrayList<>(); list.add(minVal); list.add(maxVal); res.add(list); continue; } } if (idx > 0) { minVal = arr.get(idx - 1); } List list2 = new ArrayList<>(); list2.add(minVal); list2.add(maxVal); res.add(list2); } return res; } public void dfs(TreeNode root, List arr) { if (root == null) { return; } dfs(root.left, arr); arr.add(root.val); dfs(root.right, arr); } // 寻找第一个大于等于 target 的数据 public int binarySearch(List arr, int target) { int low = 0, high = arr.size(); while (low < high) { int mid = low + (high - low) / 2; if (arr.get(mid) >= target) { high = mid; } else { low = mid + 1; } } return low; } ``` ## 查询树中环的长度（2509） ```java public int[] cycleLengthQueries(int n, int[][] queries) { int m = queries.length; int[] ans = new int[m]; for (int i = 0; i < m; ++i) { int a = queries[i][0], b = queries[i][1]; // 交换，保证 a < b if (a > b) { int tmp = a; a = b; b = tmp; } // 计算 a 和 b 的高度差（两个二进制数的位数差就是它们的高度差） int d = Integer.numberOfLeadingZeros(a) - Integer.numberOfLeadingZeros(b); // 把 b 右移 d 位后得到 b'，这样 b' 就和 a 在同一层了 // 如果此时 a == b'，说明 a 就是 a 和 b 的 LCA，答案为 d + 1 // 如果此时 a != b'，计算 a 异或 b' 的结果为 R，R 的二进制长度为 L，那么 a 和 b' 需要各上跳 L 步才能到达 LCA，答案为 d + 2L + 1 ans[i] = d + (32 - Integer.numberOfLeadingZeros(a ^ (b >> d))) * 2 + 1; } return ans; } ``` ## 二叉树中的第 K 大层和（2583） ```java public long kthLargestLevelSum(TreeNode root, int k) { List ansList = new ArrayList<>(); Queue queue = new LinkedList<>(); queue.offer(root); while (!queue.isEmpty()) { int size = queue.size(); long sum = 0; for(int i = 0; i < size; i++) { TreeNode node = queue.poll(); sum += node.val; if (node.left != null) queue.offer(node.left); if (node.right != null) queue.offer(node.right); } ansList.add(sum); } if (ansList.size() < k) return -1; Collections.sort(ansList); return ansList.get(ansList.size() - k); } ``` ### 二叉树 框架代码 ```java private void traverse(TreeNode node) { // 前序遍历 traverse(node.left); // 中序遍历 traverse(node.right); // 后序遍历 } ``` #### [124. 二叉树中的最大路径和](https://leetcode.cn/problems/binary-tree-maximum-path-sum/) - 题目：二叉树中的 **路径** 被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 **至多出现一次** 。该路径 **至少包含一个** 节点，且不一定经过根节点。 **路径和** 是路径中各节点值的总和。 给你一个二叉树的根节点 `root` ，返回其 **最大路径和** 。 - 难度：困难 - 题解 ```java public class _124_二叉树中的最大路径和 { int ans = Integer.MIN_VALUE; public int maxPathSum(TreeNode root) { maxGain(root); return ans; } /** * 获取当前节点的最大贡献值 * * 前置概念 * 树中最大路径和：从任意节点出发 的最大路径和（可以不包括当前节点），也是本题的解 * 最大贡献值：从当前节点出发 的最大路径和（一定包含当前节点） * * 采用后续遍历，会遍历树中所有节点，并在遍历的过程中求 树中最大路径和。 * 时间复杂度：O(n) * 空间复杂度：O(n) * @param node * @return 当前节点最大路径和 = 当前节点的贡献值 + max(左子节点最大路径和, 右子节点最大路径和) */ private int maxGain(TreeNode node) { if (node == null) return 0; // 递归计算左右子节点的最大贡献值（如果为负数，返回 0） int leftSum = Math.max(maxGain(node.left), 0); int rightSum = Math.max(maxGain(node.right), 0); // 当前节点的最大贡献值 取决于该节点的值与该节点的左右子节点的 最大贡献值 int tmpMax = node.val + leftSum + rightSum; // 更新 树中最大路径和 ans = Math.max(ans, tmpMax); // 返回当前节点的最大贡献值 return node.val + Math.max(leftSum, rightSum); } } ``` 相似题型 [687. 最长同值路径](https://leetcode.cn/problems/longest-univalue-path/) #### [105. 从前序与中序遍历序列构造二叉树](https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/) - 题目：给定两个整数数组 `preorder` 和 `inorder` ，其中 `preorder` 是二叉树的**先序遍历**， `inorder` 是同一棵树的**中序遍历**，请构造二叉树并返回其根节点。 - 难度：中等 - 题解： ```java public class _105_从前序与中序遍历序列构造二叉树 { public TreeNode buildTree(int[] preorder, int[] inorder) { int n = preorder.length; // 存储中序遍历值与位置，用于快速定位中序遍历根节点位置 Map iMap = new HashMap<>(); for (int i = 0; i < n; i++) { iMap.put(inorder[i], i); } // 确认好迭代边界很重要（到底是 左闭右开 还是 左闭右闭） return build(preorder, 0, n - 1, inorder, 0, n - 1, iMap); } /** * 根据 preorder[pStart, pEnd] 和 inorder[iStart, iEnd] 创建根节点，并构建子树（将子树连接到根节点） * * 解法：前序遍历 * 时间复杂度：O(n) * 空间复杂度：O(n) * * 提示：前序遍历有课找到根节点，中序遍历可以获取左右子树大小 * * @param pArray 前序遍历 * @param pStart 前序遍历起始索引 * @param pEnd 前序遍历终止索引 * @param iArray 中序遍历 * @param iStart 中序遍历起始索引 * @param iEnd 中序遍历终止索引 * @param iMap key：中序遍历中的值， val：对应索引 * @return 构建树的根节点 */ public TreeNode build(int[] pArray, int pStart, int pEnd, int[] iArray, int iStart, int iEnd, Map iMap) { if (pStart > pEnd) return null; // 前序遍历中的第一个节点就是根节点 // 获取中序遍历跟节点索引 int iRoot = iMap.get(pArray[pStart]); // 创建根节点 TreeNode root = new TreeNode(pArray[pStart]); // 获取左子树节点数量 int leftSize = iRoot - iStart; // 构造左子树，并连接到根节点 // pStart: 前序遍历，根节点索引 // pStart + 1: 前序遍历，左子树起始位置 // pStart + leftSize: 前序遍历，左子树终止位置 // iStart: 中序遍历，左子树起始位置 // rootIdxInIn: 中序遍历，根节点索引 // rootIdxInIn - 1: 中序遍历，左子树终止位置 root.left = build(pArray, pStart + 1, pStart + leftSize, iArray, iStart, iRoot - 1, iMap); // 构造右子树，并连接到根节点 // pStart: 前序遍历，根节点索引 // pStart + leftSize + 1: 前序遍历，右子树起始位置 // pEnd: 前序遍历，右子树终止位置 // rootIdxInIn + 1: 中序遍历，右子树起始位置 // rootIdxInIn: 中序遍历，根节点索引 // iEnd: 中序遍历，右子树终止位置 root.right = build(pArray, pStart + leftSize + 1, pEnd, iArray, iRoot + 1, iEnd, iMap); return root; } } ``` #### [99. 恢复二叉搜索树](https://leetcode.cn/problems/recover-binary-search-tree/) - 题目：给你二叉搜索树的根节点 `root` ，该树中的 **恰好** 两个节点的值被错误地交换。*请在不改变其结构的情况下，恢复这棵树* 。 - 难度：中等 - 题解1 ``` ``` ### 动态规划 框架代码 ```java // 初始化 base case dp[0][0][...] = base case; for 状态1 in 状态1的所有取值 for 状态2 in 状态2的所有取值 for ... dp[状态1][状态2][...] = 求最值(选择1, 选择2, ...) ``` 如何列出正确的状态转移方程 - 确定 base case - 确定 “状态”，也就是原问题和子问题中的变量 - 确定 “选择”，也就是导致 “状态”产生变化的行为 - 明确 dp 函数 / 数组 的定义 #### 322.凑零钱问题 ### 回溯算法 框架代码 ```java List result = new ArrayList<>(); private void backtrack(路径, 选择列表) { if 满足结束条件 { result.add(路径); return } for 选择 in 选择列表 // 做选择 backtrack(路径, 选择列表); // 撤销选择 } ``` 重要的 3 个问题 - 路径，已经做出的选择 - 选择列表，当前可做的选择 - 结束条件，到达决策树底层，无法再做选择的条件 #### 46.全排列问题 #### 51.N 皇后问题 ### BFS 算法套路框架 BFS 找到的路径一定是最短的 BFS 比 DFS 空间复杂度高 框架代码 ```java public int BFS(Node start, Node target) { // 存放待访问路径 Queue q = new LinkedList<>(); // 记录访问路径，防止走回头路 Set visited = new HashSet<>(); // 加入起点 q.offer(start); visited.add(start); // 记录步数 int step = 0; while (!q.isEmpty()) { // 遍历待访问层 int sz = q.size(); for(int i = 0; i < sz; i++) { TreeNode cur = q.poll(); // 是否找到路径 if (cur == target) return step; for(Node n : cur 相邻节点) { if (!visited.contains(n)){ q.offer(n); visited.add(n); } } } step++; } return depth; } ``` #### 111.二叉树的最小高度 #### 752.解开密码锁的最少次数 #### 876.寻找无环单链表的中点 #### 剑指offer22.寻找单链表的倒数第 k 个元素 #### 1.两数之和 ### 双指针 #### 141.判定链表中是否含有环 #### 142.已知这个链表中含有环，返回这个环的起始位置 ### 二分查找 #### 框架代码 ```java int binarySearch(int[] nums, int target) { int low = 0, high = nums.length(); while (...) { int mid = low + (high - low / 2); if (nums[mid] == target) { ...; }else if (nums[mid] < target) { left = ... } else if (nums[mid] > target) { right = ... } } return ...; } ``` #### 简单实现 - 迭代 ```java private int binarySearch(int[] nums, int target) { int low = 0, high = nums.length - 1; while (low <= high) { int mid = low + (high - low) / 2; if (nums[mid] == target) { return mid; } else if (nums[mid] < target) { low = mid + 1; } else { high = mid - 1; } } return -1; } ``` #### 简单实现 - 递归 ```java public int binarySearch2(int[] nums, int target) { return doSearch(nums, 0, nums.length - 1, target); } private int doSearch(int[] nums, int low, int high, int target) { if (low > high) return -1; int mid = low + ((high - low) >> 1); if (nums[mid] == target) { return mid; } else if (nums[mid] < target) { return doSearch(nums, mid+1, high, target); } else { return doSearch(nums, low, mid-1, target); } } ``` #### 4 种变体 ```java /** * @param nums 待查询数组 * @param target 待查询值 * @return * @description 变体一：查找第一个等于给定值的元素 * @author Karson Wang * @date 2020/4/27 11:16 */ public int findFirst(int[] nums, int target) { int low = 0, high = nums.length - 1; while (low <= high) { int mid = low + ((high - low) >> 1); if (nums[mid] == target) { if ((mid == 0) || (nums[mid - 1] != target)) { return mid; } else { high = mid - 1; } } else if (nums[mid] < target) { low = mid + 1; } else { high = mid - 1; } } return -1; } /** * @param nums 待查询数组 * @param target 待查询值 * @return * @description 变体二：查找最后一个等于给定值的元素 * @author Karson Wang * @date 2020/4/27 11:16 */ public int findLast(int[] nums, int target) { int low = 0, high = nums.length - 1; while (low <= high) { int mid = low + ((high - low) >> 1); if (nums[mid] == target) { if ((mid == nums.length - 1) || (nums[mid + 1] != target)) { return mid; } else { low = mid + 1; } } else if (nums[mid] < target) { low = mid + 1; } else { high = mid - 1; } } return -1; } /** * @param nums 待查询数组 * @param target 待查询值 * @return * @description 变体三：查找第一个大于等于给定值的元素 * @author Karson Wang * @date 2020/4/27 11:16 */ public int findFirstBig(int[] nums, int target) { int low = 0, high = nums.length - 1; while (low <= high) { int mid = low + ((high - low) >> 1); // 通过夹逼法实现(最终使 nums[high] < target, 此时如果 nums[low] >= value 则返回 low) if (nums[mid] >= target) { high = mid - 1; } else { low = mid + 1; } } // return low < nums.length && nums[low] >= target ? low : -1; } /** * @param nums 待查询数组 * @param target 待查询值 * @return * @description 变体四：查找最后一个小于等于给定值的元素 * @author Karson Wang * @date 2020/4/27 11:16 */ public int findLastSmall(int[] nums, int target) { int low = 0, high = nums.length - 1; while (low <= high) { int mid = low + ((high - low) >> 1); // 通过夹逼法实现(最终使 nums[low] > target, 此时如果 a[high] <= value 则返回 high) if (nums[mid] <= target) { low = mid + 1; } else { high = mid - 1; } } // return high >= 0 && nums[high] <= target ? high : -1; } ``` ### 滑动窗口 框架代码 ```java void slidingWindow(String s, String t) { // key：目标字符串 t 中包含的字符，val：该字符出现次数 Map need = new HashMap<>(); // key：当前窗口包含的目标字符，val：该字符出现次数 Map window = new HashMap<>(); // 初始化 need for (Character c : t.toCharArray()) { need.put(c, need.getOrDefault(c, 0) + 1); } // 窗口边界 [left, right) int left = 0, right = 0; // 窗口中目标字符达标数量 int valid = 0; // right 没有到达原字符串 s 的右边界 while (right < s.length()) { // c 是准备加入窗口的字符 char c = s.charAt(right); // 右移窗口 right++; // 进行窗口内数据的一系列更新 ... // debug 输出的位置 System.out.printf("window: [%d, %d]\n", left, right); // 判断窗口左侧是否要收缩 while (valid == need.size()) { // d 是将移出窗口的字符 char d = s.charAt(left); // 左移窗口 left++; // 进行窗口内数据的一系列更新 ... } } } ``` #### [76. 最小覆盖子串](https://leetcode.cn/problems/minimum-window-substring/) - 题目：给你一个字符串 `s` 、一个字符串 `t` 。返回 `s` 中涵盖 `t` 所有字符的最小子串。如果 `s` 中不存在涵盖 `t` 所有字符的子串，则返回空字符串 `""` - 难度：困难 ```java ``` #### [567. 字符串的排列](https://leetcode.cn/problems/permutation-in-string) #### [438. 找到字符串中所有字母异位词](https://leetcode.cn/problems/find-all-anagrams-in-a-string) #### [3. 无重复字符的最长子串](https://leetcode.cn/problems/longest-substring-without-repeating-characters) 极客时间 - 数据结构与算法之美 #### 数据结构 1. 数组 2. 链表 3. [栈](https://gitee.com/Karson-Wang/geektime-algo/tree/master/src/main/java/com/karson/geektime/algo/stack) 4. [队列](https://gitee.com/Karson-Wang/geektime-algo/tree/master/src/main/java/com/karson/geektime/algo/queue) 5. [跳表] 6. [散列表] #### 排序 1. [冒泡](https://gitee.com/Karson-Wang/geektime-algo/blob/master/src/main/java/com/karson/geektime/algo/sort/Bubble.java) 2. [插入](https://gitee.com/Karson-Wang/geektime-algo/blob/master/src/main/java/com/karson/geektime/algo/sort/Insertion.java) 3. [选择](https://gitee.com/Karson-Wang/geektime-algo/blob/master/src/main/java/com/karson/geektime/algo/sort/Selection.java) 4. [快排](https://gitee.com/Karson-Wang/geektime-algo/blob/master/src/main/java/com/karson/geektime/algo/sort/Quick.java) 5. [归并](https://gitee.com/Karson-Wang/geektime-algo/blob/master/src/main/java/com/karson/geektime/algo/sort/Merge.java) 6. 桶 7. [计数](https://gitee.com/Karson-Wang/geektime-algo/blob/master/src/main/java/com/karson/geektime/algo/sort/Counting.java) 8. 基数 #### 查找 1. [二分查找](https://gitee.com/Karson-Wang/geektime-algo/blob/master/src/main/java/com/karson/geektime/algo/search/BinarySearch.java) 4. [哈希算法] 12. [字符串匹配] 13. [Trie树] 14. [AC自动机] 15. [贪心算方法] 16. [分治算法] 17. [回溯算法] 18. [动态规划] #### 树 1. [二叉树](https://gitee.com/Karson-Wang/geektime-algo/blob/master/src/main/java/com/karson/geektime/algo/tree/BinaryTree.java) 2. [二叉查找树](https://gitee.com/Karson-Wang/geektime-algo/blob/master/src/main/java/com/karson/geektime/algo/tree/BinarySearchTree.java) 3. [红黑树] 4. [递归树] 5. [堆和堆排序] #### 图 1. [图] #### 搜索 1. [深度优先搜索] 2. [广度优先搜索] # 知识点索引 ## 二叉树 ### 遍历方式 - 94 - 迭代 - 递归 - Morris ### 二叉搜索树的定义 - 95 ### 分类 - 116 - Perfect Binary Tree - Complete Binary Tree - Full/Strictly Binary Tree ### AVL 树 - 230 题 ​ AVL 树是平衡二叉查找树，在数据结构和算法分类中 ## 二分查找 ### 二分查找的写法与4中常见变体 - 222