class037 二叉树高频题目-下-不含树型dp【算法】
code1 236. 二叉树的最近公共祖先
// 普通二叉树上寻找两个节点的最近公共祖先
// 测试链接 : https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/
package class037; // 普通二叉树上寻找两个节点的最近公共祖先 // 测试链接 : https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/ public class Code01_LowestCommonAncestor { // 不提交这个类 public static class TreeNode { public int val; public TreeNode left; public TreeNode right; } // 提交如下的方法 public static TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { if (root == null || root == p || root == q) { // 遇到空，或者p，或者q，直接返回 return root; } TreeNode l = lowestCommonAncestor(root.left, p, q); TreeNode r = lowestCommonAncestor(root.right, p, q); if (l != null && r != null) { // 左树也搜到，右树也搜到，返回root return root; } if (l == null && r == null) { // 都没搜到返回空 return null; } // l和r一个为空，一个不为空 // 返回不空的那个 return l != null ? l : r; } }
code2 235. 二叉搜索树的最近公共祖先
// 搜索二叉树上寻找两个节点的最近公共祖先
// 测试链接 : https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-search-tree/
package class037; // 搜索二叉树上寻找两个节点的最近公共祖先 // 测试链接 : https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-search-tree/ public class Code02_LowestCommonAncestorBinarySearch { // 不提交这个类 public static class TreeNode { public int val; public TreeNode left; public TreeNode right; } // 提交如下的方法 public static TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { // root从上到下 // 如果先遇到了p，说明p是答案 // 如果先遇到了q，说明q是答案 // 如果root在p~q的值之间，不用管p和q谁大谁小，只要root在中间，那么此时的root就是答案 // 如果root在p~q的值的左侧，那么root往右移动 // 如果root在p~q的值的右侧，那么root往左移动 while (root.val != p.val && root.val != q.val) { if (Math.min(p.val, q.val) < root.val && root.val < Math.max(p.val, q.val)) { break; } root = root.val < Math.min(p.val, q.val) ? root.right : root.left; } return root; } }
code3 113. 路径总和 II
// 收集累加和等于aim的所有路径
// 测试链接 : https://leetcode.cn/problems/path-sum-ii/
package class037; import java.util.ArrayList; import java.util.List; // 收集累加和等于aim的所有路径 // 测试链接 : https://leetcode.cn/problems/path-sum-ii/ public class Code03_PathSumII { // 不提交这个类 public static class TreeNode { public int val; public TreeNode left; public TreeNode right; } // 提交如下的方法 public static List<List<Integer>> pathSum(TreeNode root, int aim) { List<List<Integer>> ans = new ArrayList<>(); if (root != null) { List<Integer> path = new ArrayList<>(); f(root, aim, 0, path, ans); } return ans; } public static void f(TreeNode cur, int aim, int sum, List<Integer> path, List<List<Integer>> ans) { if (cur.left == null && cur.right == null) { // 叶节点 if (cur.val + sum == aim) { path.add(cur.val); copy(path, ans); path.remove(path.size() - 1); } } else { // 不是叶节点 path.add(cur.val); if (cur.left != null) { f(cur.left, aim, sum + cur.val, path, ans); } if (cur.right != null) { f(cur.right, aim, sum + cur.val, path, ans); } path.remove(path.size() - 1); } } public static void copy(List<Integer> path, List<List<Integer>> ans) { List<Integer> copy = new ArrayList<>(); for (Integer num : path) { copy.add(num); } ans.add(copy); } }
code4 110. 平衡二叉树
// 验证平衡二叉树
// 测试链接 : https://leetcode.cn/problems/balanced-binary-tree/
package class037; // 验证平衡二叉树 // 测试链接 : https://leetcode.cn/problems/balanced-binary-tree/ public class Code04_BalancedBinaryTree { // 不提交这个类 public static class TreeNode { public int val; public TreeNode left; public TreeNode right; } // 提交如下的方法 public static boolean balance; public static boolean isBalanced(TreeNode root) { // balance是全局变量，所有调用过程共享 // 所以每次判断开始时，设置为true balance = true; height(root); return balance; } // 一旦发现不平衡，返回什么高度已经不重要了 public static int height(TreeNode cur) { if (!balance || cur == null) { return 0; } int lh = height(cur.left); int rh = height(cur.right); if (Math.abs(lh - rh) > 1) { balance = false; } return Math.max(lh, rh) + 1; } }
code5 98. 验证二叉搜索树
// 验证搜索二叉树
// 测试链接 : https://leetcode.cn/problems/validate-binary-search-tree/
code1 中序遍历判断是否升序
code2 递归
package class037; // 验证搜索二叉树 // 测试链接 : https://leetcode.cn/problems/validate-binary-search-tree/ public class Code05_ValidateBinarySearchTree { // 不提交这个类 public static class TreeNode { public int val; public TreeNode left; public TreeNode right; } // 提交以下的方法 public static int MAXN = 10001; public static TreeNode[] stack = new TreeNode[MAXN]; public static int r; // 提交时改名为isValidBST public static boolean isValidBST1(TreeNode head) { if (head == null) { return true; } TreeNode pre = null; r = 0; while (r > 0 || head != null) { if (head != null) { stack[r++] = head; head = head.left; } else { head = stack[--r]; if (pre != null && pre.val >= head.val) { return false; } pre = head; head = head.right; } } return true; } public static long min, max; // 提交时改名为isValidBST public static boolean isValidBST2(TreeNode head) { if (head == null) { min = Long.MAX_VALUE; max = Long.MIN_VALUE; return true; } boolean lok = isValidBST2(head.left); long lmin = min; long lmax = max; boolean rok = isValidBST2(head.right); long rmin = min; long rmax = max; min = Math.min(Math.min(lmin, rmin), head.val); max = Math.max(Math.max(lmax, rmax), head.val); return lok && rok && lmax < head.val && head.val < rmin; } }
code6 669. 修剪二叉搜索树
// 修剪搜索二叉树
// 测试链接 : https://leetcode.cn/problems/trim-a-binary-search-tree/
package class037; // 修剪搜索二叉树 // 测试链接 : https://leetcode.cn/problems/trim-a-binary-search-tree/ public class Code06_TrimBinarySearchTree { // 不提交这个类 public static class TreeNode { public int val; public TreeNode left; public TreeNode right; } // 提交以下的方法 // [low, high] public static TreeNode trimBST(TreeNode cur, int low, int high) { if (cur == null) { return null; } if (cur.val < low) { return trimBST(cur.right, low, high); } if (cur.val > high) { return trimBST(cur.left, low, high); } // cur在范围中 cur.left = trimBST(cur.left, low, high); cur.right = trimBST(cur.right, low, high); return cur; } }
code7 337. 打家劫舍 III
// 二叉树打家劫舍问题
// 测试链接 : https://leetcode.cn/problems/house-robber-iii/
package class037; // 二叉树打家劫舍问题 // 测试链接 : https://leetcode.cn/problems/house-robber-iii/ public class Code07_HouseRobberIII { // 不提交这个类 public static class TreeNode { public int val; public TreeNode left; public TreeNode right; } // 提交如下的方法 public static int rob(TreeNode root) { f(root); return Math.max(yes, no); } // 全局变量，完成了X子树的遍历，返回之后 // yes变成，X子树在偷头节点的情况下，最大的收益 public static int yes; // 全局变量，完成了X子树的遍历，返回之后 // no变成，X子树在不偷头节点的情况下，最大的收益 public static int no; public static void f(TreeNode root) { if (root == null) { yes = 0; no = 0; } else { int y = root.val; int n = 0; f(root.left); y += no; n += Math.max(yes, no); f(root.right); y += no; n += Math.max(yes, no); yes = y; no = n; } } }
