目录
217.数组存在重复元素
与剑指Offer第11题类似。很简答
class Solution {
public boolean containsDuplicate(int[] nums) {
HashSet<Integer> hashSet = new HashSet<>();
for (int num : nums) {
if (hashSet.contains(num)) {
return true;
}else hashSet.add(num);
}
return false;
}
}//居然可以用工具类
class Solution {
public boolean containsDuplicate(int[] nums) {
//先排序
Arrays.sort(nums);
//然后比较相邻数字
for (int i = 0; i < nums.length - 1; ++i) {
if (nums[i] == nums[i + 1]) {
return true;
}
}
return false;
}
}53.最大子序和（难）
-
贪心算法
-
动态规划（空间换时间）
比较当前求和和加上一个新的值之间的大小，谁大 当前值就是更新谁的
class Solution {
public int maxSubArray(int[] nums) {
int cur = 0;
int summax = nums[0];
for (int num : nums) {
cur = Math.max(num,cur+num);
summax = Math.max(cur,summax);
}
return summax;
}
}1.两数之和
-
哈希表
实现高效查找的数据结构：
哈希表的k-v使用数学上的【质数分辨定理】进化成哈希树，达到遍历次数很少情况下查找出内容。
遍历数组每个x值 ， 在hashtable中找对应了target-x的值
好处：放到哈希表保证x值不会在和自己比较。等于数组只遍历了一遍
因为答案肯定存在所以，通过哈希表 值和索引 通过kv查找 极快。
class Solution {
public int[] twoSum(int[] nums, int target) {
HashMap<Integer, Integer> hashMap = new HashMap<>();
for (int i = 0;i<nums.length;i++){
if (hashMap.containsKey(target-nums[i])){
return new int[] {i , hashMap.get(target - nums[i])};
}
hashMap.put(nums[i],i);
}
return new int[0];
}
}88.合并两个有序数组
-
合并然后排序即可
快速排序的时间复杂度是对数级的复杂度（m+n）O(m+n)
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
//把值都替换了
for(int i = m;i<m+n;i++){
nums1[i] = nums2[i-m];
}
//再排序
Arrays.sort(nums1);
}
}-
利用已经排序的性质，比较头部元素即可
通过双指针和三目运算符进行比较替换就行。
数组拷贝用clone或者syatem.arraycopy()
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
int[] nums1_copy = new int[m + n];
System.arraycopy(nums1,0,nums1_copy,0,m);
int p1 = 0;
int p2 = 0;
int cur = 0;
//去除m为0的情况。
if (m ==0) System.arraycopy(nums2,0,nums1,0,n);
//两个同时满足时
while ((p1<m) && (p2<n))
nums1[cur++] = nums1_copy[p1]<nums2[p2]? nums1_copy[p1++]:nums2[p2++];
//一定会有先遍历完的情况
if (p1<m)
System.arraycopy(nums1_copy,p1,nums1,p1+p2,m+n-p1-p2);
if (p2<n)
System.arraycopy(nums2,p2,nums1,p1+p2,m+n-p2-p1);
}
}350.两个数组的交集II
有多个变量 例如值和次数 就要想到用哈希
单个数组某个值出现的次数其实就是上限，另一个觉都不可以比他多。
class Solution {
public int[] intersect(int[] nums1, int[] nums2) {
//哈希表查找速度很快，也不用比较。所以用这个存 值和次数 一堆k,v
HashMap<Integer, Integer> hashMap = new HashMap<>();
//先遍历短的放到哈希表中
for (int i : nums1) {
int count = hashMap.getOrDefault(i,0)+1;
hashMap.put(i,count);
}
//定义一个数组和索引去存交集
int[] inter = new int[nums1.length];
int index = 0;
//遍历第二个数组看值和哈希表中有没有重复，有的话加入新得数组中去，并且次数还>0就更新次数-1。否则就删除
for (int i : nums2) {
int count = hashMap.getOrDefault(i, 0);
if (count>0){
inter[index++] = i;
count--;
if (count>0){
hashMap.replace(i,count);
}else hashMap.remove(i);
}
}
//最后把新数组从0道索引拷贝一个新得返回，因为一开始的容量是随便定的。
return Arrays.copyOfRange(inter,0,index);
}
}-
排序+双指针；更快
小的自己用，相等一移，一个数组超过了就遍历结束。
121. 买卖股票的最佳时机
-
双循环暴力算法 用时过长，没有意义。
-
动态规划
//动态规划
class Solution {
public int maxProfit(int[] prices) {
int minPrice = Integer.MAX_VALUE;
int maxProfit = 0;
for (int i = 0;i<prices.length;i++){
//确定哪一天卖只需要明确这一天之前哪一天是最小值就行
if (prices[i]<minPrice){
minPrice = prices[i];
//然后确定这一天来卖
}else if (prices[i]-minPrice>maxProfit){
maxProfit = prices[i]-minPrice;
}
}
return maxProfit;
}
}118.杨辉三角形
找到每一行和数字的关系就行。不就是最左最右确定了，中间的等于上面两个之和嘛。理解就行
class Solution {
public List<List<Integer>> generate(int numRows) {
//这个大数组放数组
ArrayList<List<Integer>> lists = new ArrayList<>();
//定义每一行
for (int i = 0;i<numRows;i++){
//每一行new一个小数组放数字
ArrayList<Integer> array = new ArrayList<>();
//j=i是因为第几行就有几个数字
for (int j = 0;j<=i;j++){
if (j == 0||j==i){
array.add(1);
}else array.add(lists.get(i-1).get(j-1)+lists.get(i-1).get(j));
}
lists.add(array);
}
return lists;
}
}566.重复矩阵（reshape）
-
矩阵重塑最重要的就是元素总数对列取整为行；对列取余为列。
class Solution {
public int[][] matrixReshape(int[][] mat, int r, int c) {
//一定要拿到内层的列大length
int a = mat.length;
int b = mat[0].length;
int[][] reshapeMatrix = new int[r][c];
if (a*b == r*c){
for (int x= 0;x<r*c;x++){
//核心代码
reshapeMatrix[x/c][x%c] = mat[x/b][x%b];
}
}else return mat;
return reshapeMatrix;
}
}36.有效数独（看起来太困了）
class Solution {
public boolean isValidSudoku(char[][] board) {
//定义数字行内出现的次数
int[][] row = new int[9][9];
//定义数字列内出现的次数
int[][] column = new int[9][9];
//定义数字九宫格内出现的次数最大为9次
int[][][] jiugongge = new int[3][3][9];
//遍历数组
for (int i =0;i <9;i++){
for(int j = 0;j<9;j++){
char c = board[i][j];
//只要存在数字
if (c !='.'){
//把数字-1化成索引下标,c是字符串要减去字符串，-1会报错。
int index = c-'1';
//这个时候++意思是第i行这个c值次数+1，默认row第二位就是{1-9}-1；每一行都有可能是1-9
//例如现在是第一行第一列是9，就在row[1][8]号位置+1
row[i][index]++;
//列同理
column[j][index]++;
//并且九宫格内次数也要+1,例如也是第1行第一列，i/3 j/3会自动定位到所在的小宫格
jiugongge[i/3][j/3][index]++;
//次数大于1就不成立一个数独
if (row[i][index]>1||column[j][index]>1||jiugongge[i/3][j/3][index]>1) return false;
}
}
}
return true;
}
}73.矩阵置零
boolean 才是基本数据类型 Boolean不是！
通过true判断 不要通过0判断。
虽然这个不是最好的方法 但也也足够了。
class Solution {
public void setZeroes(int[][] matrix) {
int m = matrix.length;
int n = matrix[0].length;
//只能是小写的
//拿到行列尺寸
boolean[] row = new boolean[m];
boolean[] col = new boolean[n];
for (int i = 0;i<m;i++){
for (int j = 0;j<n;j++){
if (matrix[i][j] == 0) {
//拿到哪些行列为0，设为true是这个解法的关键
//这一行和这一列都为true,为后续判断
row[i] = col[j] = true;
}
}
}
//同样双循环遍历，没什么可说的，很无脑
for (int i = 0; i<m ;i++){
for (int j = 0; j<n ;j++){
//这里不用0判断是为了 防止 变成0以后判断又对了，全都为0了。用过布尔判断，是0后全部为0
if (row[i] || col[j]){
matrix[i][j] =0;
}
}
}
}
}387. 字符串中的第一个唯一字符
map存次数 利用getOrDefault 自增就好了，次数为1的第一个值输出索引
class Solution {
public int firstUniqChar(String s) {
//放到HashMap中
HashMap<Character, Integer> hashMap= new HashMap<Character, Integer>();
//遍历每个char
for (int i = 0;i < s.length();i++){
char c = s.charAt(i);
//就表示次数自增
hashMap.put(c,hashMap.getOrDefault(c,0)+1);
}
//从前往后取
for (int i = 0;i < s.length();i++){
if (hashMap.get(s.charAt(i))==1) return i;
}
return -1;
}
}方法二存索引
其实就是发挥一个k=v的关系可以和for循环一起用
hashmap是乱序的。得保证每次更细都得小于index
class Solution {
public int firstUniqChar(String s) {
Map<Character, Integer> hashMap = new HashMap<Character, Integer>();
int n = s.length();
//通过方法charAt，利用索引下标按顺序取值 第一次取就put 值和索引，如果还有同样的字母，直接覆盖v为-1
for (int i = 0; i < n; ++i) {
char c = s.charAt(i);
if (hashMap.containsKey(c)) {
hashMap.put(c, -1);
} else {
hashMap.put(c, i);
}
}
//定义第一次出现的索引，定义为字符串尺寸，为了让最后一位也满足
int index = n;
for (Map.Entry<Character, Integer> entry : hashMap.entrySet()) {
//hashmap是乱序的，所以取值都是随便拿的。
int value = entry.getValue();
//由于是乱序的，所以不仅要保证他只出现了一次也就是（！=-1）,也要满足只能往小了更新。后面的值不能比这个index大。
if (value != -1 && value<index) {
index = value;
}
}
//如果全都是-1，就没有更新
if (index == n) {
index = -1;
}
return index;
}
}383.赎金信
简单解法(非常简单，好理解)
class Solution {
public boolean canConstruct(String ransomNote, String magazine) {
//把杂志的字母和次数全部拿到
HashMap<Character, Integer> hashMap = new HashMap<>();
for (int i = 0;i<magazine.length();i++){
char c = magazine.charAt(i);
//计次数，自加1。
hashMap.put(c,hashMap.getOrDefault(c,0)+1);
}
//匹配map有没有msg需要的字母和个数
for (int i = 0;i<ransomNote.length();i++){
char c = ransomNote.charAt(i);
//没字母或者没次数了就false
if ((!hashMap.containsKey(c))||(hashMap.get(c)<1)) return false;
else {
hashMap.put(c,hashMap.get(c)-1);
}
}
//前面正常运行，那么就true
return true;
}
}-
高级一点的，快速一点的
字母 - ’a‘ 就可以变成字母0-25的的索引下标了
class Solution {
public boolean canConstruct(String ransomNote, String magazine) {
int[] array = new int[26];
for (int i = 0;i<magazine.length();i++){
array[magazine.charAt(i)-'a']++;
}
for (int i = 0;i<ransomNote.length();i++){
//先减减再判断 没有字母就是-1了
if (--array[ransomNote.charAt(i)-'a']<0) return false;
}
return true;
}
}242.有效的字母异位词
最简单的就是383题反向再来一遍，四个循环就结束了，家人们。
-
改进一（首选）
class Solution {
public boolean isAnagram(String s, String t) {
int[] array1 = new int[26];
for (int i = 0;i<s.length();i++){
array1[s.charAt(i)-'a']++;
}
for (int i = 0;i<t.length();i++){
//先减减再判断 没有字母就是-1了
if (--array1[t.charAt(i)-'a']<0) return false;
}
//再用一个循环就可以
for (int i =0;i<array1.length;i++){
//没有全部消除就是false
if (array1[i]>0) return false;
}
return true;
}
}-
改进二（排序）
首先异味词 他的长度肯定是相等的；
并且排序以后是一模一样的。
用Arrays这个工具类进行数组的排序和数组的对比
string变成数组，利用Arrays.sort 和Arrays.equals
class Solution {
public boolean isAnagram(String s, String t) {
//长度不相等 直接false
if(s.length() != t.length()) {return false;}
//将字符串变成数组调用Arrays
char[] chars = s.toCharArray();
char[] chart = t.toCharArray();
Arrays.sort(chars);
Arrays.sort(chart);
return Arrays.equals(chars,chart);
}
}141.环形链表
链表查询效率低，但随机增删效率高
链表总结(倒数k个原元素，中间元素，有没有环)
-
思路和数组重复一样，但是很慢
class Solution {
public boolean hasCycle(ListNode head) {
HashSet<ListNode> listNodes = new HashSet<>();
//循环访问
while (head!= null){
//HashSet不能添加重复的元素，当调用add（Object）方法时候，
//首先会调用Object的hashCode方法判hashCode是否已经存在，如不存在则直接插入元素；存在则用equals再判断
//true 表示存入成功，false表示存入失败
if (!listNodes.add(head)){//存入失败 表示有 就说明有环
return true;
}head = head.next;
}
return false;
}
}-
双指针很快而且空间复杂度就1
class Solution {
public boolean hasCycle(ListNode head) {
//不能为空，也不能只有一个节点
if (head == null|| head.next==null)return false;
ListNode slow = head;
//快指针比慢指针多走一步（一开始先拉一个身位）
ListNode fast = head.next;
//一直循环 找到相等为止
while (slow != fast){
//一旦有null就停止循环
if (fast==null || fast.next==null){
return false;
}
slow = slow.next;
//每一次再多走一步，只要能追上你就是有环了（每一次再多跑一步）
fast = fast.next.next;
}
//找到相等了，自然就停止循环了。
return true;
}
}21.合并两个有序链表（看不太懂）
-
递归函数必须要有终止条件，否则会出错；
-
递归函数先不断调用自身，直到遇到终止条件后进行回溯，最终返回答案。
方法一：递归
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l1 == null) {
return l2;
} else if (l2 == null) {
return l1;
} else if (l1.val < l2.val) {
//然后下一个继续和l2比
l1.next = mergeTwoLists(l1.next, l2);
//谁小就返回谁
return l1;
} else {
l2.next = mergeTwoLists(l1, l2.next);
return l2;
}
}
}方法二：迭代（暴力循环解决）
基本数据类型 传值 引用数据类型 传地址
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode listNode = new ListNode(-1);
//这是一个指针，可以不停的位置，对pre赋值就是再改变listNode；
ListNode pre = listNode;
while (l1!=null&& l2!=null){
if (l1.val <= l2.val){
pre.next=l1;
l1 = l1.next;
}
else {
pre.next=l2;
l2 = l2.next;
}
pre = pre.next;
}
pre.next = l1==null?l2:l1;
return listNode.next;
}
}203.移除链表元素
-
增加了虚拟头节点
class Solution {
public ListNode removeElements(ListNode head, int val) {
if(head==null) return head;
ListNode newListNode = new ListNode(0);
//防止他第一个值就有问题
newListNode.next = head;
//为了不去动这个新创的东西 通过引用来改变每个节点值
ListNode pre = newListNode;
while (pre.next!=null){
if (pre.next.val == val){
pre.next = pre.next.next;
}
else {
pre = pre.next;
}
}
return newListNode.next;
}
}-
不增加虚拟头节点，那就的判断头节点。
class Solution {
public ListNode removeElements(ListNode head, int val) {
//删除值相同的头结点后，可能新的头结点也值相等，用循环解决
while(head!=null&&head.val==val){
head=head.next;
}
if(head==null)
return head;
ListNode prev=head;
//确保当前结点后还有结点
while(prev.next!=null){
if(prev.next.val==val){
prev.next=prev.next.next;
}else{
prev=prev.next;
}
}
return head;
}
}206.反转链表
class Solution {
public ListNode reverseList(ListNode head) {
//双指针
ListNode pre = null;
ListNode cur = head;
while(cur != null){
ListNode next = cur.next;
//指向前一个pre点
cur.next = pre;
//往前动
pre = cur;
//往前动
cur = next;
}
return pre;
}
}83.删除链表中的重复元素
result帮head动地址
但返回的还是head；
因为result一直动到后面去了。
class Solution {
public ListNode deleteDuplicates(ListNode head) {
if (head == null) return head;
ListNode result = head;
while (result.next !=null){
if (result.val ==result.next.val){
//算往前动了,不用再额外动了。不相等，才到else里面再动。
result.next = result.next.next;
}else {
result = result.next;
}
}
return head;
}
}20.有效的括号
-
通过栈来实现 Deque就是一个LinkList，有push，pop，peek方法
class Solution {
public boolean isValid(String s) {
//只有偶数和>0的字符串才可以判断
if (s.length() % 2 != 0||s.length() == 0)return false;
//创建一个hashmap存括号对应的值
HashMap<Character, Character> hashMap = new HashMap<>();
hashMap.put(')','(');
hashMap.put(']','[');
hashMap.put('}','{');
//创建一个双线链表
Deque<Character> deque = new LinkedList<>();
for (int i =0;i<s.length();i++){
char c = s.charAt(i);
//如果是对应的括号，只要栈不为空，并且最上面的值等于hashmap对应的value就返回true
if (hashMap.containsKey(c)){
if (deque.isEmpty() || deque.peek()!=hashMap.get(c)){
return false;
}else {
deque.pop();
}
//没有这个元素就压栈
}else {
deque.push(c);
}
}
//最后都弹完了
return deque.isEmpty();
}
}232.用栈实现队列
通过双栈实现队列，栈是先进后出。
把deque1的数据先弹到deque2，后进的数压到deque1中再把deque2的数值弹回来。一来一回数据顺序就会反过来了。
class MyQueue {
private Deque<Integer> deque1;
private Deque<Integer> deque2;
private int popNum;
private int peekNum;
private boolean isEmpty;
public MyQueue() {
deque1 = new LinkedList<Integer>();
deque2 = new LinkedList<Integer>();
}
public void push(int x) {
while (!deque1.isEmpty()){
deque2.push(deque1.pop());
}
deque1.push(x);
while (!deque2.isEmpty()){
deque1.push(deque2.pop());
}
}
public int pop() {
if (!deque1.isEmpty()) {
popNum = deque1.peek();
deque1.pop();
return popNum;
}
return 0;
}
public int peek() {
if (!deque1.isEmpty()) {
peekNum = deque1.peek();
return peekNum;
}
return 0;
}
public boolean empty() {
if (deque1.isEmpty()) {
return true;
}
return false;
}
}144.二叉树的前序排列
根节点——左子树——右子树的方式遍历这棵树
先根节点，然后下面从左开始，然后再右全部
用递归的方式，从左节点开始遍历。
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
//创建一个列表存数字
ArrayList<Integer> res = new ArrayList<>();
preorder(root,res);
return res;
}
//传一个节点，和一个列表，把节点值传进去，然后下一个节点
private void preorder(TreeNode root, ArrayList<Integer> res) {
//迭代都有一个迭代终止条件
if (root == null) return;
res.add(root.val);
//先左节点，递归
preorder(root.left,res);
//才到右节点
preorder(root.right,res);
}
}94.二叉树的中序排列
左子树——根节点——右子树的方式遍历这棵树
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
ArrayList<Integer> res = new ArrayList<>();
order(root,res);
return res;
}
private void order(TreeNode root, ArrayList<Integer> res) {
if (root==null) return;
order(root.left,res);
res.add(root.val);
order(root.right,res);
}
}102.二叉树的层序排列
-
DFS（Deep First Search）深度优先搜索。
-
BFS（Breath First Search）广度优先搜索。
DFS用递归的形式，用到了栈结构，先进后出。
BFS选取状态用队列的形式，先进先出。
此题为广度优先算法：
-
先以层的方式拿数据，打印看看
-
然后再套上循环，加层数
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
//避免空指针异常
if(root == null) {
return new ArrayList<List<Integer>>();
}
ArrayList<List<Integer>> res = new ArrayList<List<Integer>>();
Queue<TreeNode> queue = new LinkedList<TreeNode>();
//先加头节点
queue.offer(root);
while(!queue.isEmpty()){
//计算每层弹出的个数
int count = queue.size();
//每一层加一个list
res.add(new ArrayList<Integer>());
for(int i =0;i<count;i++){
//先进先出拿到值
TreeNode node = queue.peek();
//每层对应的索引下标位置
res.get(res.size()-1).add(node.val);
//弹出去
queue.poll();
//拿下一层
if (node.left != null){
queue.offer(node.left);
}
if (node.right != null){
queue.offer(node.right);
}
}
}
return res;
}
}104.二叉树的最大深度
-
使用层序排列，返回层数即可。
class Solution {
public int maxDepth(TreeNode root) {
if (root == null) return 0;
Queue<TreeNode> queue = new LinkedList<>();
int res = 0;
queue.offer(root);
while (!queue.isEmpty()){
int size = queue.size();
for (int i =0;i<size;i++) {
TreeNode node = queue.poll();
if (node.left !=null){
queue.offer(node.left);
}
if (node.right !=null){
queue.offer(node.right);
}
}
res++;
}
return res;
}
}-
深度优先算法（递归）
这个更快！空间换时间！
class Solution {
public int maxDepth(TreeNode root) {
//终止条件
if (root == null) return 0;
//返回值和单层逻辑
else {
int left = maxDepth(root.left);
int right = maxDepth(root.right);
//往下走一步就得加1
return 1+Math.max(left,right);
}
}
}101.对称二叉树
递归
class Solution {
public boolean isSymmetric(TreeNode root) {
//先判断空值
if (root == null){
return true;
}
//不空才递归
else{
return comp(root.left,root.right);
}
}
//定迭代遍量和返回值
public boolean comp(TreeNode node1,TreeNode node2){
//终止条件
if (node1 == null && node2 == null) {
return true;
}
else if (node1 == null || node2 == null || node1.val != node2.val) {
return false;
}
//单层循环条件
boolean outside = comp(node1.left,node2.right);
boolean inside = comp(node1.right,node2.left);
//内外同时满足
boolean res = outside&&inside;
return res;
}
}-
迭代（很慢也很笨的方法）
class Solution {
public boolean isSymmetric(TreeNode root) {
if (root == null){
return true;
}
//然后一个一个放进来，从外面开始弹
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root.left);
queue.offer(root.right);
while(!queue.isEmpty()){
//按顺序，从外侧弹出去
TreeNode node1 = queue.poll();
TreeNode node2 = queue.poll();
if(node1 == null &node2 ==null){
continue;
}
if(node1 == null||node2==null||node1.val != node2.val){
return false;
}
//走到这里说明都不为空，且左右相等,然后不停的加，排队等着判断，从外往内
queue.offer(node1.left);
queue.offer(node2.right);
queue.offer(node1.right);
queue.offer(node2.left);
}
return true;
}
}226.反转二叉树
仔细看下题目的 输入 和 输出，输出的左右子树的位置跟输入正好是相反的，于是我们可以递归的交换左右子树来完成这道题。
先翻最底层 再反转上一层，这不就是递归了一定要先观察规律。
class Solution {
public TreeNode invertTree(TreeNode root) {
//终止条件
if(root == null) return null;
invertTree(root.left);
invertTree(root.right);
//单层逻辑,就是把2，7给换了
TreeNode tmp = root.right;
root.right = root.left;
root.left = tmp;
return root;
}
}-
迭代
class Solution {
public TreeNode invertTree(TreeNode root) {
if(root==null) {
return null;
}
//将二叉树中的节点逐层放入队列中，再迭代处理队列中的元素
LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
queue.add(root);
while(!queue.isEmpty()) {
//每次都从队列中拿一个节点，并交换这个节点的左右子树
TreeNode tmp = queue.poll();
TreeNode left = tmp.left;
tmp.left = tmp.right;
tmp.right = left;
//如果当前节点的左子树不为空，则放入队列等待后续处理
if(tmp.left!=null) {
queue.add(tmp.left);
}
//如果当前节点的右子树不为空，则放入队列等待后续处理
if(tmp.right!=null) {
queue.add(tmp.right);
}
}
//返回处理完的根节点
return root;
}
}112.路径总和（背）
-
广度优先，我把所有类和可能全部拿到。
class Solution {
public boolean hasPathSum(TreeNode root, int targetSum) {
//如果节点为空，返回null。
if (root == null) {
return false;
}
//一个存节点，一个存sum
Queue<TreeNode> queueNode = new LinkedList<TreeNode>();
Queue<Integer> queueNodeVal = new LinkedList<Integer>();
queueNode.offer(root);
queueNodeVal.offer(root.val);
while (!queueNode.isEmpty()) {
//1.节点和值都弹出去
TreeNode node = queueNode.poll();
Integer nodeVal = queueNodeVal.poll();
//3.如果到叶节点了，左右都null了。一个一个弹出来，判断是否相等，相等true，不相等则循环继续。
//如果没到叶节点就会不停往下走，就不管这个if
if (node.left == null && node.right == null) {
if (nodeVal == targetSum) {
return true;
}
continue;
}
//2.左边/右边有货就加进来，然后val累加，
//这一步是走到每一层的数据都会放在队列中
if (node.left != null) {
queueNode.offer(node.left);
queueNodeVal.offer(node.left.val + nodeVal);
}
if (node.right != null) {
queueNode.offer(node.right);
queueNodeVal.offer(node.right.val + nodeVal);
}
}
return false;
}
}-
递归（深度优先）
class Solution {
public boolean hasPathSum(TreeNode root, int targetSum) {
//额外条件：如果节点为空，返回null。
if (root == null) {
return false;
}
//1.走到叶节点了（这是递归终止条件，不到叶节点，这一步也不执行）
//2.不断的减targetSum，
//判断减完的值与叶节点是否相等。(单层条件)
if (root.left == null && root.right == null){
if (targetSum == root.val){
return true;
}else return false;
}
// '||'表示或者同时进行。
return hasPathSum(root.left,targetSum-root.val) ||hasPathSum(root.right,targetSum-root.val);
}
}700.二叉搜索树中的搜索
首先，学习二叉搜索树：
什么是二叉搜索树？
二叉搜索树是一棵二叉树，每个节点都有以下特性：
-
大于左子树上任意一个节点的值，
-
小于右子树上任意一个节点的值。
-
注意：只跟你上一个节点相比
一个二叉搜索树的例子：
二叉搜索树有经典算法就是：查找，插入和删除！
-
迭代
class Solution {
public TreeNode searchBST(TreeNode root, int val) {
//循环不停迭代值，直到满足条件后直接返回root
while (root != null && root.val != val) {
root = root.val < val? root.right:root.left;
}
return root;
}
}-
递归
class Solution {
public TreeNode searchBST(TreeNode root, int val) {
//1.递归终止条件
if(root == null || root.val ==val){
return root;
}
//2.单层逻辑，根据大小继续往下找就行。
return root.val<val?searchBST(root.right,val) : searchBST(root.left,val);
}
}701.二叉搜索树中的插入操作（中等）
不是从上到下按顺序的，是看你插入先来后到，后到的就跟上一个节点比就行了。
比如55，33，现在插入44，44比55小，放左边，但是左边有33了所以往后排，44大于33，所以放33右边。
class Solution {
public TreeNode insertIntoBST(TreeNode root, int val) {
if (root == null) {
return new TreeNode(val);
}
//一开始先复制节点
TreeNode pos=root;
while(pos!=null){
//比你大
if (val > pos.val){
//并且你右边为null，直接加然后停止循环了
if (pos.right == null){
TreeNode node = new TreeNode(val);
pos.right = node;
break;
//如果右边有货，那就往下走
}else {
pos = pos.right;
}
}else {
if (pos.left == null){
TreeNode node = new TreeNode(val);
pos.left = node;
break;
//如果左边有货，那就往下走
}else {
pos = pos.left;
}
}
}
return root;
}
}98.验证二叉搜索树
-
递归
不能只考虑局部节点的左右大小，还要考虑整个大局观。所以只有判断条件，然后不停的往下走肯定就不对了。
必须要有上下界限的概念。
class Solution {
public boolean isValidBST(TreeNode root) {
//每次递归就会自动给最大最小值赋值，在这里赋值。不要再递归里面写死了。
return recursion(root,Long.MIN_VALUE,Long.MAX_VALUE);
}
private boolean recursion(TreeNode root,long lower,long upper){
//1.递归终止条件
if(root == null){
return true;
}
//2.单层逻辑+相等也不满足
if(root.val>=upper || root.val<=lower){
return false;
}
//3.自己定义的参数是变量，可以带着变量继续到下一个递归，不能把lower/upper在这里就写死了。
return recursion(root.left,lower,root.val)&&recursion(root.right,root.val,upper);
}
}-
中序搜索
一句话解释就是，中序遍历去搜索 二叉搜索树时得到的一定值升序排列。
class Solution {
long pre = Long.MIN_VALUE;
public boolean isValidBST(TreeNode root) {
//中序遍历方法
if(root == null){
return true;
}
//写在前面有终止条件的所以要加if和return
if(!isValidBST(root.left)){
return false;
}
if(root.val<=pre){
return false;
}
//更新pre。
pre = root.val;
//返回右边true/false。
return isValidBST(root.right);
}
}653.两数之和Ⅳ-输入BST
-
最笨的方法（1+94题）
class Solution {
public boolean findTarget(TreeNode root, int k) {
//创建数组
ArrayList<Integer> nums = new ArrayList<>();
order(root,nums);
//找值
HashSet<Integer> sites = new HashSet<Integer>();
for (int i = 0;i<nums.size();i++){
if(sites.contains(k-nums.get(i))){
return true;
}
sites.add(nums.get(i));
}
return false;
}
private void order(TreeNode root, ArrayList<Integer> res) {
if (root==null) return;
order(root.left,res);
res.add(root.val);
order(root.right,res);
}
}-
边找遍加+递归
class Solution {
public boolean findTarget(TreeNode root, int k) {
HashSet<Integer> sets = new HashSet<Integer>();
return recursion(root,k,sets);
}
private boolean recursion(TreeNode root, int k,HashSet sets){
//1.终止条件
if(root ==null){
return false;
}
//2.有我就true，没有就add
if(sets.contains(k-root.val)){
return true;
}
sets.add(root.val);
//3.单层逻辑，往左右两边走
return recursion(root.left, k,sets)||recursion(root.right,k,sets);
}
}235.二叉搜索树的最近公共祖先
-
两次遍历
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
//拿到两个节点的路径节点和，有长有短。按顺序排的
List<TreeNode> pathNodes_P = pathNodes(root,p);
List<TreeNode> pathNodes_Q = pathNodes(root,q);
//定义最近公共节点
TreeNode a = null;
for(int i = 0;i<pathNodes_P.size()&&i<pathNodes_Q.size();i++){
//从头开始相等就覆盖，不相等就下一个，直到全部遍历完
if(pathNodes_P.get(i) == pathNodes_Q.get(i)){
//覆盖上一次的相等节点，离最近又进了一点。
a = pathNodes_P.get(i);
}else{
break;
}
}
//然后返回循环后最后一次相等的节点就是最近公共节点
return a;
}
private List<TreeNode> pathNodes (TreeNode root,TreeNode target){
//把所有走过的节点都放进去
List<TreeNode> lists = new ArrayList<TreeNode>();
TreeNode node = root;
//如果等于目标节点就停止循环
while(node != target){
//加入进来
lists.add(node);
if(node.val<target.val){
node = node.right;
}else{
node = node.left;
}
}
//把目标节点加入进来
lists.add(node);
return lists;
}
}-
一次两个点同时遍历
利用了二叉搜索树的特点：右边都大于节点，左边都小于节点。中间就是分叉点
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
//这一步可有可无。一般不对原值动手，另起一个变量赋值比较好。
TreeNode a = root;
//无限循环迭代配合终止条件终止就可以了，因为一定有公共节点，所以一定会结束
while(true){
if(a.val>p.val && a.val>q.val){
a = a.left;
}
else if(a.val<p.val && a.val<q.val){
a = a.right;
}
else{
//结束循环。
break;
}
}
return a;
}
}