class037 二叉树高频题目-下-不含树型dp【算法】

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) {// 左树也搜到，右树也搜到，返回rootreturn 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是全局变量，所有调用过程共享// 所以每次判断开始时，设置为truebalance = 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;// 提交时改名为isValidBSTpublic 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;// 提交时改名为isValidBSTpublic 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;}}}