import java.util.*; public class Solution { // 时间复杂度要求O(logn)，使用二分查找 // 因为数组原本是有序的，旋转之后，分为了两部分 // 前面部分一定都大于后面部分 // 这时使用二分查找，如果nums[mid]的值大于nums[right]，则表示测试mid在前一部分，需要将left = mid + 1 // 如果nums[mid] < nums[right]，则表示mid在后面一部分，需要将right = mid; // 如果nums[mid] == nums[right]，需要不断缩小right的值，来缩小氛围 public...

import java.util.*; public class Solution { // 数字在升序数组中出现的次数 // 思路：因为数组是升序排列的，所以只需要找到目标值的最左侧索引和最右侧索引就可以找到整个目标值出现的次数 // 因为数组中全是整数，所以可以考虑用二分查找法找到k+0.5和k-0.5出现的位置，两者相减就是k出现的次数 public int GetNumberOfK (int[] nums, int k) { // write code here return binarySearch(nums,k+0.5) - binarySearch(nums,k-0.5); } ...

import java.util.*; public class Solution { public boolean flag = false; public int lowestCommonAncestor (TreeNode root, int p, int q) { // write code here ArrayList<Integer> listP = new ArrayList<>(); ArrayList<Integer> listQ = new ArrayList<>(); dfs(root,listP,p); flag = fa...

import java.util.*; public class Solution { // 给定一颗二叉树找到对应两个节点的最近公共祖先 // 要使用路径记录的话，需要用到回溯的方法，回溯就是出栈 public boolean flag = false; public int lowestCommonAncestor (TreeNode root, int o1, int o2) { // write code here ArrayList<Integer> path1 = new ArrayList<>(); ArrayList<Integer> pat...

import java.util.*; public class Solution { // 重点在于使用pre来保存当前节点的前一个节点 public TreeNode head = null; public TreeNode pre = null; public TreeNode Convert(TreeNode pRootOfTree) { // 整体的思路还是中序遍历递归，先Convert(root.left)再写逻辑处理，最后递归遍历右子树Convert(root.rieght) if(pRootOfTree == null) return null; // 首先递归到最左最小值，以...

import java.util.*; /** public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; } } */ public class Solution { // 重点在于使用pre来保存当前节点的前一个节点 public TreeNode head = null; public TreeNode pre = null; public TreeNode Convert(TreeNode pRoo...

import java.util.*; public class Solution { // 方法：搜索路径比较 // 因为题中的二叉搜索树没有相同的结点，因此分别从根节点往下利用二叉搜索树较大的数在右子树，较小的数在左子树，可以轻松找到p、q public int lowestCommonAncestor (TreeNode root, int p, int q) { // write code here ArrayList<Integer> listP = new ArrayList<>(); ArrayList<Integer> listQ = new...

import java.util.*; public class Solution { // 根据栈的压入顺序，判断第二个序列是否为该栈的弹出序列 // 思路：通过模拟栈的方式来解决，将压入序列视为栈，将弹出序列视为队列 // 对于压入序列，每次压入后，检查栈顶元素是否等于队列队头元素，如果等于，则分别弹出栈顶元素和队列队头元素 // 直到栈为空或者栈顶元素不等于队列队头元素 // 当所有的压入序列都被遍历后，可以直接依次比较栈内元素与队列元素的值，如果存在不一样的顺序，则表示判断失败 public boolean IsPopOrder (int[] pushV, int[] popV) { ...

import java.util.*; public class Solution { // 从上到下按层打印二叉树的val值，返回值为一个二维列表 // 思路：bfs遍历二叉树，同时记录下当前层的节点数，以便插入对应行的二维列表中 public ArrayList<ArrayList<Integer>> Print (TreeNode pRoot) { if(pRoot == null) return new ArrayList<>(); // write code here ArrayList<ArrayList<Integer>&gt...

import java.util.*; public class Solution { // 判断平衡二叉树， // 思路：平衡二叉树，要保证所有左右子树的高度差不能大于1 // 1. 计算树的高度 // 2. 计算左右子树的高度差 // 3. 使用bfs遍历所有子树 public boolean IsBalanced_Solution (TreeNode pRoot) { // write code here // 如果是空树，也属于平衡二叉树 if(pRoot == null) return true; Queue<TreeNode> queue = new LinkedLis...

import java.util.*; public class Solution { public boolean VerifySquenceOfBST(int[] sequence) { // 处理空数组的情况 if (sequence == null || sequence.length == 0) { return false; } return judge(sequence, 0, sequence.length - 1); } // 使用索引范围而不是复制数组，提高效率 private boolean judge(int[] sequence, int start, int end...

import java.util.*; public class Solution { // 二叉搜索树的后序遍历序列，判断某数组是否为某二叉搜索树的后序遍历 // 二叉搜索树特性：左子树的所有节点都小于根节点，右子树所有节点都大于根节点；中序遍历是有序的 // 后序遍历：左右根 // 数组中最后的节点一定是根节点 // 思路：根据最后一个节点时根节点，划分出左子树和右子树，左子树全部小于根节点，右子树全部大于根节点。划分完了之后，因为我们是根据第一个大于根节点的元素进行划分的，所以只需要验证划分出来的右子树全部大于根节点。之后递归进行这一过程 public boolean VerifySqu...

import java.util.*; public class Solution { // 二叉搜索树的后序遍历序列，判断某数组是否为某二叉搜索树的后序遍历 // 二叉搜索树特性：左子树的所有节点都小于根节点，右子树所有节点都大于根节点；中序遍历是有序的 // 后序遍历：左右根 // 数组中最后的节点一定是根节点 // 思路：根据最后一个节点时根节点，划分出左子树和右子树，左子树全部小于根节点，右子树全部大于根节点。划分完了之后，因为我们是根据第一个大于根节点的元素进行划分的，所以只需要验证划分出来的右子树全部大于根节点。之后递归进行这一过程 public boolean VerifySqu...

import java.util.*; import java.util.ArrayList; public class Solution { // 层次遍历输出所有节点，空节点不输出 public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) { ArrayList<Integer> list = new ArrayList<>(); if(root == null) return list; Queue<TreeNode> queue = new LinkedList<&g...