施工企业税收筹划,seo自动刷外链工具,推荐就业的培训机构,朝阳区互联网大厂class037 二叉树高频题目-下-不含树型dp【算法】 code1 236. 二叉树的最近公共祖先
// 普通二叉树上寻找两个节点的最近公共祖先 // 测试链接 : https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/
package class037;// 普通二叉树上寻找两个节点的最近…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 ListListInteger pathSum(TreeNode root, int aim) {ListListInteger ans new ArrayList();if (root ! null) {ListInteger path new ArrayList();f(root, aim, 0, path, ans);}return ans;}public static void f(TreeNode cur, int aim, int sum, ListInteger path, ListListInteger 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(ListInteger path, ListListInteger ans) {ListInteger 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;}}}
