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...

import java.util.*; public class Solution { // 使用BFS，层次自上而下每次交换左右子树 public TreeNode Mirror (TreeNode pRoot) { // write code here if(pRoot == null) return null; Queue<TreeNode> queue = new LinkedList<>(); queue.add(pRoot); while(!queue.isEmpty()){ TreeNode node = queue.poll(); // 先将当前结点的正...

import java.util.*; public class Solution { // 将左子树变为右子树 public TreeNode Mirror (TreeNode pRoot) { // write code here if(pRoot == null) return null; // 后序递归，左右根 // 先深度最左端的节点，遇到空树返回，处理最左端的两个子节点交换位置 // 然后进入右子树，继续按照左右根的方式访问 // 最后回到根节点交换根节点的两个子树。 TreeNode left = Mirror(pRoot.left); TreeNode right = Mirr...

import java.util.*; public class Solution { // 理由栈先进后出的特性，来进行字符串的反转 // 要注意的是，str中只是单词的顺序反了，不是字母整体的顺序反了。 // 思路：首先要将单词根据空格进行分割，之后对单词的顺序进行翻转。 public String ReverseSentence(String str) { if(str.length() == 0 || str.length() == 1) return str; String[] strs = str.split(" "); Stack<String> ...

import java.util.*; public class Solution { // 根据前序遍历和中序遍历来重建二叉树 // 前序序列可以找到每一个树（子树）的根节点，中序遍历可以根据根节点的位置分出左右子树的所有节点 // 通过递归，可以完整重建二叉树 public TreeNode reConstructBinaryTree (int[] preOrder, int[] vinOrder) { // 注意这里的递归出口条件，整个过程中preorder和vinorder的长度都是一样的，当长度为0时就代表树已经被重建好了 if(preOrder.length == 0 ) retu...

import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param proot TreeNode类 * @param k int整型 * @return int整型 */ // 二叉搜索树的第k小的结点 // 思路：首先获取到中序排列的list，之后根据二叉搜索树中序排列有序的特性，list.get(k)就能找到第k小的节点值 // 注意要判断异常情况 List<TreeNode> list = new ArrayList<>(); pub...

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 { // 找树的深度，使用dfs，递归的思想，就是分别从根节点遍历左子树和右子树，来比较左右子树的深度， public int TreeDepth(TreeNode root) { if(root == null){ return 0; } r...

import java.util.*; /* public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; } } */ public class Solution { // 判断是否含有环的话，需要双指针遍历，有重合的话就是有环 // 这里是如果有环的话，要返回环的入口结点 // 更简单了，只需要一个指针，每次将一个结点放入hashmap，如果被放入的结点已经存在了，则表示存在环，且这个第一个被判存在的结点就是环的入口 public ListNode EntryNodeOf...

import java.util.*; /* public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; } }*/ public class Solution { // 双指针的方法，分别遍历两个链表，当其中任意一个指针到达对应的链表末尾后，重定向到另一个链表的头部 // 这样可以想象为将连个链表合二为一，不用纠结两个链表长度不一的情况 // 如果两个链表没有公共结点，则指针会同时到达另一个链表尾部的null的位置 // 如果有公共节点，则指针会同时到达第一个公共结点 p...

import java.util.*; import java.util.Stack; public class Solution { Stack<Integer> s1 = new Stack<>(); Stack<Integer> s2 = new Stack<>(); public void push(int node) { s1.push(node); // 这里的重点是s2.peek() >= node，需要将等于当前最小值的值也加入到s2中，这样可以确保与s1中与最小值相等的元素数量一致。 if(s2.isEmpty() || ...