中学建设校园网站方案,手机网站做安卓客户端,静态网页制作期末试卷及答案,网站建设 成本练习地址 面试必刷101-牛客1、链表反转2、链表内指定区间反转**3. 链表中的节点每k个一组翻转**4、**合并两个排序的链表**5、**合并k个已排序的链表**6、**判断链表中是否有环****7、链表中环的入口结点**8、链表中倒数最后k个结点**9、删除链表的倒数第n个节点****10、两个链…练习地址 面试必刷101-牛客1、链表反转2、链表内指定区间反转**3. 链表中的节点每k个一组翻转**4、**合并两个排序的链表**5、**合并k个已排序的链表**6、**判断链表中是否有环****7、链表中环的入口结点**8、链表中倒数最后k个结点**9、删除链表的倒数第n个节点****10、两个链表的第一个公共结点****11、链表相加(二)**12、两数相加13、字符串相加14、二进制求和15、36进制相加**16、单链表的排序****17、判断一个链表是否为回文结构****18、判断是否为回文字符串**19、最长回文字符串**20、链表的奇偶重排****21、删除有序链表中重复的元素-I****22、删除有序链表中重复的元素-II**23、二分查找-I循环结束条件总结**24、二维数组中的查找****25、寻找峰值****24、数组中的逆序对**25、旋转数组的最小数字26、比较版本号**27、二叉树的前序遍历****28、二叉树的中序遍历**29、二叉树的后序遍历**30、求二叉树的层序遍历****31、按之字形顺序打印二叉树**32、二叉树的最大深度**33、二叉树中和为某一值的路径(一)****34、二叉搜索树与双向链表**35、**对称的二叉树****36、合并二叉树**37、**二叉树的镜像****38、判断是不是二叉搜索树****39、判断是不是完全二叉树****40、判断是不是平衡二叉树**41、**二叉搜索树的最近公共祖先****42、在二叉树中找到两个节点的最近公共祖先****43、序列化二叉树****44、重建二叉树****45、输出二叉树的右视图**1、链表反转
/*
public class ListNode {int val;ListNode next null;ListNode(int val) {this.val val;}
}*/
public class Solution {public ListNode ReverseList(ListNode head) {ListNode last null;ListNode next null;while(head ! null){next head.next;head.next last;//反转last head;//更新装态head next;}return last;}
}2、链表内指定区间反转
import java.util.*;public class Solution {public ListNode reverseBetween (ListNode head, int m, int n) {// write code hereListNode dummy new ListNode(-1);dummy.next head;ListNode left dummy;ListNode right dummy;//走到m的前一个位置for (int i 0; i m - 1; i) {left left.next;}right left;ListNode start left.next;//right要走到n的位置上for (int i 0; i n - m 1; i) {right right.next;}ListNode next right.next;//将n处的next置空right.next null;left.next reverse(start);//修正startstart.next next;return dummy.next;}public ListNode reverse(ListNode head) {ListNode last null;ListNode next null;while (head ! null) {next head.next;head.next last;last head;head next;}return last;}
}3. 链表中的节点每k个一组翻转
public class Solution {/**** param head ListNode类* param k int整型* return ListNode类*/public ListNode reverseKGroup (ListNode head, int k) {// write code hereListNode dummy new ListNode(-1);dummy.next head;ListNode left dummy;ListNode right dummy;while (right ! null) {for (int i 0; i k ; i) {right right.next;if (right null) return dummy.next;}ListNode start left.next;ListNode next right.next;right.next null;//指向反转后的结点left.next myrevser(start);//修正指针错误start.next next;//重新指向下一个k分组的前一个节点left start;right left;}return dummy.next;}public ListNode myrevser(ListNode head) {ListNode last null;ListNode next null;while (head ! null) {next head.next;head.next last;last head;head next;}return last;}
}4、合并两个排序的链表
/*
public class ListNode {int val;ListNode next null;ListNode(int val) {this.val val;}
}*/
public class Solution {public ListNode Merge(ListNode list1, ListNode list2) {if (list1 null) return list2;if (list2 null) return list1;ListNode help new ListNode(Integer.MIN_VALUE);ListNode cur help;while (list1 ! null list2 ! null) {if (list1.val list2.val) {cur.next list1;list1 list1.next;} else {cur.next list2;list2 list2.next;}cur cur.next;}cur.next list1 null ? list2 : list1;return help.next;}
}5、合并k个已排序的链表
import java.util.*;
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) {* val x;* next null;* }* }*/
public class Solution {public ListNode mergeKLists(ArrayListListNode lists) {return merger(lists, 0, lists.size() - 1);}public ListNode merger(ArrayListListNode lists, int l, int r) {if (l r) return lists.get(l);if (l r) return null;int mid (l r) 1;ListNode leftmerge merger(lists, l, mid);ListNode rightmerge merger(lists, mid 1, r);return mergerTowList(leftmerge, rightmerge);}public ListNode mergerTowList(ListNode left,ListNode right){if (left null) return right;if (right null) return left;ListNode help new ListNode(Integer.MIN_VALUE);ListNode cur help;while(left ! null right ! null){if(left.val right.val){cur.next left;left left.next;}else{cur.next right;right right.next;}cur cur.next;}cur.next left null ? right : left;return help.next;}
}6、判断链表中是否有环
public class Solution {public boolean hasCycle(ListNode head) {if(head null) return false;ListNode fast head;ListNode slow head;while(fast ! null fast.next ! null){fast fast.next.next;slow slow.next;if(slow fast) return true;}return false;}
}使用两个指针fast\textit{fast}fast 与 slow\textit{slow}slow。它们起始都位于链表的头部。随后slow\textit{slow}slow指针每次向后移动一个位置而 fast\textit{fast}fast指针向后移动两个位置。如果链表中存在环则 fast\textit{fast}fast指针最终将再次与 slow\textit{slow}slow指针在环中相遇。
7、链表中环的入口结点
使用两个指针fast\textit{fast}fast 与slow\textit{slow}slow。它们起始都位于链表的头部。随后slow\textit{slow}slow指针每次向后移动一个位置而 fast\textit{fast}fast指针向后移动两个位置。如果链表中存在环则 fast\textit{fast}fast指针最终将再次与slow\textit{slow}slow指针在环中相遇。当发现fast\textit{fast}fast 与slow\textit{slow}slow相遇时将fast\textit{fast}fast指向链表头部随后它和slow\textit{slow}slow每次向后移动一个位置。最终它们会在入环点相遇。
public class Solution {public ListNode EntryNodeOfLoop(ListNode pHead) {if(pHead null) return null;ListNode fast pHead;ListNode slow pHead;while(fast ! null fast.next ! null){fast fast.next.next;slow slow.next;if(slow fast){fast pHead;while(fast ! slow){fast fast.next;slow slow.next;}return fast;}}return null;}
}8、链表中倒数最后k个结点
使用双指针则可以不用统计链表长度。
public ListNode FindKthToTail (ListNode pHead, int k) {// write code hereListNode fast pHead;ListNode slow pHead;for (int i 0; i k; i) {if(fast null) return null;fast fast.next;}while (fast ! null) {fast fast.next;slow slow.next;}return slow;}9、删除链表的倒数第n个节点
public ListNode removeNthFromEnd (ListNode head, int n) {// write code hereListNode dummy new ListNode(-1);dummy.next head;ListNode fast head;ListNode slow dummy; //将slow位置提前for (int i 0; i n ; i) {//快慢指针走到第n个节点的前一个fast fast.next;}while (fast ! null) {fast fast.next;slow slow.next;}slow.next slow.next.next;return dummy.next;}10、两个链表的第一个公共结点
public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {int length 0; // pHead1 - pHead2长度之差if (pHead1 null || pHead2 null) return null;ListNode cur1 pHead1;ListNode cur2 pHead2;while (cur1 ! null) {cur1 cur1.next;length;}while (cur2 ! null) {cur2 cur2.next;length--;}// 尾端节点不一致判断没有节点if (cur1 ! cur2) return null;// cur1表示长的那个链表cur1 length 0 ? pHead1 : pHead2;cur2 cur1 pHead1 ? pHead2 : pHead1;length Math.abs(length);// 长链表走length步for (int i 0; i length; i) {cur1 cur1.next;}// 两个链表同时走直到相遇while (cur1 ! cur2) {cur1 cur1.next;cur2 cur2.next;}return cur1;}11、链表相加(二)
本题的主要难点在于链表中数位的顺序与我们做加法的顺序是相反的为了逆序处理所有数位我们可以使用栈把所有数字压入栈中再依次取出相加。计算过程中需要注意进位的情况。
public ListNode addInList (ListNode head1, ListNode head2) {// write code hereStackInteger s1 new Stack();StackInteger s2 new Stack();//将链表中数据放入栈中while (head1 ! null) {s1.push(head1.val);head1 head1.next;}while (head2 ! null) {s2.push(head2.val);head2 head2.next;}ListNode res null; //返回的结果int carry 0; //进位// 栈不为空或者存在进位时while (!s1.isEmpty() || !s2.isEmpty() || carry ! 0) {int val1 s1.isEmpty() ? 0 : s1.pop();int val2 s2.isEmpty() ? 0 : s2.pop();int sum val1 val2 carry;carry sum / 10; // 更新进位int cur sum % 10; // 个位数字ListNode curNode new ListNode(cur);//更新结果并连线curNode.next res;res curNode;}return res;}12、两数相加
本题低位在前高位在后可以直接从头开始相加
public ListNode addTwoNumbers(ListNode head1, ListNode head2) {// write code hereListNode res new ListNode(0); //返回的结果ListNode help res;int carry 0; //进位// 栈不为空或者存在进位时while (head1!null || head2!null || carry ! 0) {int val1 head1null ? 0 : head1.val;int val2 head2null ? 0 : head2.val;int sum val1 val2 carry;carry sum / 10; // 更新进位int cur sum % 10; // 个位数字help.next new ListNode(cur);help help.next;if(head1!null) head1 head1.next;if(head2!null) head2 head2.next;}return res.next;}13、字符串相加
public String addStrings(String num1, String num2) {StringBuilder res new StringBuilder();int num1Length num1.length() - 1;int num2Length num2.length() - 1;int carry 0;//进位while (num1Length 0 || num2Length 0 || carry ! 0) {int n1 num1Length 0 ? num1.charAt(num1Length) - 0 : 0;int n2 num2Length 0 ? num2.charAt(num2Length) - 0 : 0;int sum n1 n2 carry;carry sum / 10; //更新进位int cur sum % 10; //个位上数字res.append(cur);num1Length--;num2Length--;}return res.reverse().toString();}14、二进制求和
class Solution {public String addBinary(String a, String b) {StringBuilder ans new StringBuilder();int alength a.length() - 1;int blength b.length() - 1;int carry 0;//进位while(alength 0 || blength 0 || carry ! 0){int n1 alength 0? a.charAt(alength) - 0:0;int n2 blength 0? b.charAt(blength) - 0:0;int sum n1 n2 carry;int cur sum % 2;carry sum / 2; //更新进位ans.append(cur);alength--;blength--;}return ans.reverse().toString();}
}15、36进制相加
题目
实现一个 36 进制的加法 0-9 a-z。
示例
输入[“abbbb”,“1”]输出“abbbc”
String add36Strings(String num1, String num2) {int carry 0;int i num1.length() - 1, j num2.length() - 1;StringBuilder sb new StringBuilder();while (i 0 || j 0 || carry ! 0) {int x i 0 ? getInt(num1.charAt(i)) : 0;int y j 0 ? getInt(num2.charAt(j)) : 0;int sum x y carry; //本次结果sb.append(getChar(sum % 36));carry sum / 36; //进位i--;j--;}//翻转return sb.reverse().toString();}private int getInt(char i) {if (i 0 i 9) {return i - 0;} else {return i - a 10;}}private char getChar(int i) {if (i 9) {return (char) (i 0);} else {return (char) (i - 10 a);}}16、单链表的排序
对于链表最适合的是归并排序
public class Solution {/**** param head ListNode类 the head node* return ListNode类*/public ListNode sortInList (ListNode head) {// write code here// 对于链表最适合的是归并排序if(head null) return null;return sortPartList(head);}public ListNode sortPartList(ListNode head) {if (head.next null) return head; //链表只有一个节点// 获取 mid -- 中点为slowListNode fast head, slow head;ListNode pre null;//中点的前一个节点while (fast ! null fast.next ! null) {pre slow;slow slow.next;fast fast.next.next;}pre.next null; //断开拆成两个链表ListNode leftNode sortPartList(head);ListNode rightNode sortPartList(slow);return merge(leftNode, rightNode);}public ListNode merge(ListNode left, ListNode right) {ListNode dummy new ListNode(0);ListNode help dummy;while (left ! null right ! null) {if (left.val right.val) {help.next left;left left.next;} else {help.next right;right right.next;}help help.next;}help.next left null ? right : left;return dummy.next;}
}快速方法
public ListNode sortInList (ListNode head) {// write code here//小根堆QueueListNode queue new PriorityQueue((o1, o2) - o1.val - o2.val);ListNode help new ListNode(0);ListNode temp help;while(head ! null){queue.add(head);head head.next;}while(!queue.isEmpty()){ListNode node queue.poll();node.next null;//将节点next置空temp.next node;temp temp.next;//更新}return help.next;}17、判断一个链表是否为回文结构
利用快慢指针找到中点将后半截反序两个指针从两边遍历到中点逐个比较
当慢指针走到中点时将其下一个指针赋值为null同时将后面的指针指向中点然后遍历返回true/false然后在将后面的指针改回去
public boolean isPail (ListNode head) {// write code hereListNode fast head, slow head;while (fast ! null fast.next ! null) {slow slow.next;fast fast.next.next;}// 中点即为slowslow reverse(slow);fast head;while (slow ! null) {if (slow.val ! fast.val) return false;slow slow.next;fast fast.next;}return true;}public ListNode reverse(ListNode head) {ListNode last null;ListNode next null;while (head ! null) {next head.next;head.next last;//reverselast head;head next;}return last;}18、判断是否为回文字符串
import java.util.*;public class Solution {/*** 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可** param str string字符串 待判断的字符串* return bool布尔型*/public boolean judge (String str) {// write code hereint l 0;int r str.length() - 1;while (l r) {if (str.charAt(l) ! str.charAt(r)) return false;l;r--;}return true;}
}19、最长回文字符串
step 1遍历字符串每个字符。step 2以每次遍历到的字符为中心分奇数长度和偶数长度两种情况不断向两边扩展。step 3如果两边都是相同的就是回文不断扩大到最大长度即是以这个字符或偶数两个为中心的最长回文子串。step 4我们比较完每个字符为中心的最长回文子串取最大值即可。
import java.util.*;public class Solution {/*** 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可*** param A string字符串* return int整型*/public int getLongestPalindrome (String A) {// write code hereint res 1;for (int i 0; i A.length() - 1; i) {//分为奇数和偶数两种情况res Math.max(res, Math.max(helper(A, i, i), helper(A, i, i 1)));}return res;}public int helper(String A, int begin, int end) {//每个中心点开始扩展while (begin 0 end A.length() A.charAt(begin) A.charAt(end)) {begin--;end;}//返回长度return end - begin - 1;}
}20、链表的奇偶重排
先一个左正蹬把奇数节点串一块儿再一个右鞭腿把偶数节点串一起然后啪很快啊把两个连成一条链表可以说是训练有素有bear来了
public ListNode oddEvenList (ListNode head) {// write code hereif(head null) return head;ListNode odd head;//奇数ListNode even head.next, evenHead even; //偶数while(even ! null even.next ! null){odd.next even.next;odd odd.next;even.next odd.next;even even.next;}odd.next evenHead;return head;//奇数头是head}21、删除有序链表中重复的元素-I
import java.util.*;
public class Solution {public ListNode deleteDuplicates (ListNode head) {//一次遍历//空链表if(head null) return null;//遍历指针ListNode cur head; //指针当前和下一位不为空while(cur ! null cur.next ! null){ //如果当前与下一位相等则忽略下一位if(cur.val cur.next.val) cur.next cur.next.next;//否则指针正常遍历else cur cur.next;}return head;}
}
22、删除有序链表中重复的元素-II
删除重复元素只要重复就全部给删除一个也不留
import java.util.*;
public class Solution {public ListNode deleteDuplicates (ListNode head) {//空链表if(head null) return null;ListNode dummy new ListNode(0);//在链表前加一个表头dummy.next head;ListNode helper dummy;while(helper.next ! null helper.next.next ! null){//遇到相邻两个节点值相同if(helper.next.val helper.next.next.val){int temp helper.next.val;//将所有相同的都跳过while (helper.next ! null helper.next.val temp)helper.next helper.next.next;//忽略下一位}elsehelper helper.next;}//返回时去掉表头return dummy.next;}
}
23、二分查找-I
public int search (int[] nums, int target) {// write code hereint left 0, right nums.length - 1 ;while (left right) {int mid left (right - left) / 2;int num nums[mid];if (num target) return mid;else if (num target) right mid - 1;else left mid 1;}return -1;
}循环结束条件总结
情况一
如果搜索区间[left, right]中一定有目标值索引那么循环截止条件是while(left right)
情况二
如果搜索区间[left, right]中不一定有目标值索引那么循环截止条件是while(left right)一般用于搜索区间内是否有某个值
24、二维数组中的查找
首先看四个角左上与右下必定为最小值与最大值而左下与右上就有规律了左下元素大于它上方的元素小于它右方的元素右上元素与之相反。既然左下角元素有这么一种规律相当于将要查找的部分分成了一个大区间和小区间每次与左下角元素比较我们就知道目标值应该在哪部分中于是可以利用分治思维来做。
具体做法
step 1首先获取矩阵的两个边长判断特殊情况。step 2首先以左下角为起点若是它小于目标元素则往右移动去找大的若是他大于目标元素则往上移动去找小的。step 3若是移动到了矩阵边界也没找到说明矩阵中不存在目标值。
public class Solution {public boolean Find(int target, int [][] array) {int r array.length - 1;int c 0;while(r 0 c array[0].length){int cmp array[r][c];if(cmp target) return true;else if(cmp target) r--;else c;}return false;}
}
25、寻找峰值
public class Solution {public int findPeakElement (int[] nums) {// write code hereint left 0;int right nums.length - 1;int mid;while (left right) {// 找到中间值mid (left right) 1;// 只要当前中间值 大于它的下一位说明当前处于下坡状态那么往数组的左边遍历就可以找到峰值if(nums[mid] nums[mid 1])// 因为mid 比 它下一位大所以当前mid有可能是山峰这里向左遍历的时候需要把mid包含在内right mid; else // 否则当前中间值小于等于它的下一位时说明山峰处于上坡状态向右查找就可以找到峰值// 因为mid小于它的下一位所以这里将left赋值为mid1从大的那个数开始向右查找left mid 1;}// 此时left 和 right相等时 上面的while退出// 最终返回 left 或 right都可以return right;}
}24、数组中的逆序对
public class Solution {public int InversePairs(int [] array) {//归并算法//计数条件是左边大于右边if (array null || array.length 2) return 0;return (int)process(array, 0, array.length - 1) % 1000000007;}public long process(int [] array, int left, int right) {if (left right) return 0;int mid left (right - left) / 2;long leftnum process(array, left, mid);//左边排好序long rightnum process(array, mid 1, right);//右边排好序long mergernum merge(array, left, mid,right); //利用外排序将左右两边排好序return leftnum rightnum mergernum;}public long merge(int [] array, int left, int mid, int right) {int[] help new int[right - left 1];int helpIndex 0;//外排索引int count 0;//逆序对数量int leftHead left;//左边头索引int rightHead mid 1;//右边头索引while (leftHead mid rightHead right) {if (array[leftHead] array[rightHead]) {help[helpIndex] array[leftHead];} else {help[helpIndex] array[rightHead];count count mid - leftHead 1;}}while (leftHead mid) {help[helpIndex] array[leftHead];}while (rightHead right) {help[helpIndex] array[rightHead];}//覆盖回去for (int i 0; i help.length; i) {array[left i] help[i];}return count % 1000000007;}
}25、旋转数组的最小数字
思路
旋转数组将原本有序的数组分成了两部分有序的数组因为在原始有序数组中最小的元素一定是在首位旋转后无序的点就是最小的数字。我们可以将旋转前的前半段命名为A旋转后的前半段命名为B旋转数组即将AB变成了BA我们想知道最小的元素到底在哪里。
因为A部分和B部分都是各自有序的所以我们还是想用分治来试试每次比较中间值确认目标值最小元素所在的区间。
具体做法
step 1双指针指向旋转后数组的首尾作为区间端点。step 2若是区间中点值大于区间右界值则最小的数字一定在中点右边。step 3若是区间中点值等于区间右界值则是不容易分辨最小数字在哪半个区间比如[1,1,1,0,1]应该逐个缩减右界。step 4若是区间中点值小于区间右界值则最小的数字一定在中点左边。step 5通过调整区间最后即可锁定最小值所在。
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-aMA7sX5G-1677307640258)(${img}/image-20230112124909276.png)]
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-b3jz71xM-1677307640258)(${img}/image-20230112125112145.png)]
public int minNumberInRotateArray(int [] array) {int left 0, right array.length - 1 ;while (left right) {int mid left (right - left) / 2;//区间中点值大于区间右界值则最小的数字一定在中点右边。//array[right] 是右边界if (array[mid] array[right]) left mid 1;//区间中点值小于区间右界值则最小的数字一定在中点左边。else if (array[mid] array[right]) right mid;else right--;//无法判断在哪一边 区间中点值等于区间右界值则是不容易分辨最小数字在哪半个区间比如[1,1,1,0,1]应该逐个缩减右界。}return array[left];
}26、比较版本号
具体做法
step 1利用两个指针表示字符串的下标分别遍历两个字符串。step 2每次截取点之前的数字字符组成数字即在遇到一个点之前直接取数字加在前面数字乘10的后面。因为int会溢出这里采用long记录数字step 3然后比较两个数字大小根据大小关系返回1或者-1如果全部比较完都无法比较出大小关系则返回0.
public int compare (String version1, String version2) {// write code hereint len1 version1.length(), len2 version2.length();int n1 0, n2 0;while (n1 len1 || n2 len2) {int num1 0, num2 0; //每个点间的数字while (n1 len1 version1.charAt(n1) ! .) {num1 num1 * 10 version1.charAt(n1) - 0;}while (n2 len2 version2.charAt(n2) ! .) {num2 num2 * 10 version2.charAt(n2) - 0;}//判断每个点间的数字大小if (num1 num2) return 1;else if (num1 num2) return -1;n1;n2;//跳过点}return 0;
}27、二叉树的前序遍历
//递归方式
public int[] preorderTraversal (TreeNode root) {// write code hereListInteger list new ArrayList();preorder(root, list);int[] res new int[list.size()];for (int i 0; i list.size(); i) {res[i] list.get(i);}return res;
}
public void preorder(TreeNode node, ListInteger list) {if (node null) return;list.add(node.val);preorder(node.left, list);preorder(node.right, list);
}
//非递归方式
public int[] preorderTraversal (TreeNode root) {//添加遍历结果的数组ListInteger list new ArrayList();StackTreeNode s new StackTreeNode();//空树返回空数组if(root null)return new int[0];//根节点先进栈s.push(root);while(!s.isEmpty()){//每次栈顶就是访问的元素TreeNode node s.pop();list.add(node.val);//如果右边还有右子节点进栈if(node.right ! null)s.push(node.right);//如果左边还有左子节点进栈if(node.left ! null)s.push(node.left);}//返回的结果int[] res new int[list.size()];for(int i 0; i list.size(); i)res[i] list.get(i);return res;
}28、二叉树的中序遍历
public int[] inorderTraversal (TreeNode root) {// write code here// 递归方式ListInteger list new ArrayList();inorder(root, list);int[] res new int[list.size()];for (int i 0; i list.size(); i) {res[i] list.get(i);}return res;
}
public void inorder(TreeNode root, ListInteger list) {if (root null) return;inorder(root.left, list);list.add(root.val);inorder(root.right, list);
}public int[] inorderTraversal (TreeNode root) {//非递归方式//每棵子树整棵树左边界依次进栈依次弹出处理对右树循环//添加遍历结果的数组ListInteger list new ArrayList(); StackTreeNode s new StackTreeNode();//空树返回空数组if(root null) return new int[0];//当树节点不为空或栈中有节点时while(root ! null || !s.isEmpty()){ //每次找到最左节点while(root ! null){ s.push(root);root root.left;}//访问该节点TreeNode node s.pop(); list.add(node.val); //进入右节点root node.right; }//返回的结果int[] res new int[list.size()]; for(int i 0; i list.size(); i)res[i] list.get(i);return res;
}29、二叉树的后序遍历
public int[] postorderTraversal (TreeNode root) {// write code hereListInteger list new ArrayList();postorder(root, list);int[] res new int[list.size()];for (int i 0; i list.size(); i) {res[i] list.get(i);}return res;
}
public void postorder(TreeNode root, ListInteger list) {if (root null) return;postorder(root.left, list);postorder(root.right, list);list.add(root.val);
}//非递归头入栈放入另一个栈先左后右
public int[] postorderTraversal (TreeNode root) {// write code hereListInteger list new ArrayList();StackTreeNode stack1 new Stack();StackTreeNode stack2 new Stack();stack1.push(root);if (root null) return new int[0];while (!stack1.isEmpty()) {TreeNode node stack1.pop();stack2.push(node);if (node.left ! null) {stack1.push(node.left);}if (node.right ! null) {stack1.push(node.right);}}while (!stack2.isEmpty()) {list.add(stack2.pop().val);}int[] res new int[list.size()];for (int i 0; i list.size(); i) {res[i] list.get(i);}return res;
}30、求二叉树的层序遍历
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-MHAsUcY5-1677307640261)(${img}/Untitled 23.png)]
public ArrayListArrayListInteger levelOrder (TreeNode root) {// write code hereArrayListArrayListInteger array new ArrayList();if (root null) return array;QueueTreeNode queue new LinkedList();queue.offer(root);while (!queue.isEmpty()) {ArrayListInteger temp new ArrayListInteger();int n queue.size();//该层数量while (n-- 0) {TreeNode node queue.poll();temp.add(node.val);if(node.left!null) queue.offer(node.left);if(node.right!null) queue.offer(node.right);}array.add(temp);}return array;
}31、按之字形顺序打印二叉树
public ArrayListArrayListInteger Print(TreeNode pRoot) {ArrayListArrayListInteger array new ArrayList();if (pRoot null) return array;QueueTreeNode queue new LinkedList();boolean flag true;queue.add(pRoot);while (!queue.isEmpty()) {ArrayListInteger temp new ArrayListInteger();int n queue.size();//该层数量while (n-- 0) {TreeNode node queue.poll();temp.add(node.val);if (node.left ! null) queue.add(node.left);if (node.right ! null) queue.add(node.right);}//奇数行反转偶数行不反转flag !flag;if (flag)Collections.reverse(temp);array.add(temp);}return array;
}32、二叉树的最大深度
public int maxDepth (TreeNode root) {// write code here// 递归终止if (root null) {return 0;}// dfs先递归左子结点再递归右子结点最后求出每一子树的深度的最大值return Math.max(maxDepth(root.left), maxDepth(root.right)) 1;
}public int maxDepth (TreeNode root) {// write code hereif (root null) return 0;QueueTreeNode queue new LinkedList();queue.offer(root);int res 0;while (!queue.isEmpty()) {int n queue.size();//该层数量while (n-- 0) {TreeNode node queue.poll();if (node.left ! null) queue.offer(node.left);if (node.right ! null) queue.offer(node.right);}res;}return res;
}33、二叉树中和为某一值的路径(一)
遍历的方法我们可以选取二叉树常用的递归前序遍历因为每次进入一个子节点更新sum值以后相当于对子树查找有没有等于新目标值的路径因此这就是子问题递归的三段式为
终止条件 每当遇到节点为空意味着过了叶子节点返回。每当检查到某个节点没有子节点它就是叶子节点此时sum减去叶子节点值刚好为0说明找到了路径。返回值 将子问题中是否有符合新目标值的路径层层往上返回。本级任务 每一级需要检查是否到了叶子节点如果没有则递归地进入子节点同时更新sum值减掉本层的节点值。
具体做法
step 1每次检查遍历到的节点是否为空节点空节点就没有路径。step 2再检查遍历到是否为叶子节点且当前sum值等于节点值说明可以刚好找到。step 3检查左右子节点是否可以有完成路径的如果任意一条路径可以都返回true因此这里选用两个子节点递归的或。
public class Solution {public boolean hasPathSum (TreeNode root, int sum) {// write code hereif (root null) return false;return dfs(root, sum);}public boolean dfs(TreeNode node, int target) {if (node null) return false;// 目标路径不存在开始回溯target - node.val; // 更新目标值 // 当前节点为叶子节点并且目标路径存在时返回 trueif (node.left null node.right null target 0) return true;return dfs(node.left, target) || dfs(node.right, target);}
}34、二叉搜索树与双向链表
//递归
public class Solution {private TreeNode head null;//起始位置private TreeNode pre null;//不断更新的位置public TreeNode Convert(TreeNode pRootOfTree) {if (pRootOfTree null) return null;//中序遍历即为有序Convert(pRootOfTree.left);if (head null) {head pRootOfTree;//最左端pre head;} else {pre.right pRootOfTree;//右指针指向后继pRootOfTree.left pre;//左指针指向前继pre pRootOfTree; //更新位置}Convert(pRootOfTree.right);return head;}
}//非递归
public class Solution {public TreeNode Convert(TreeNode pRootOfTree) {if (pRootOfTree null)return null;//使用非递归方式StackTreeNode s new Stack();TreeNode head null;TreeNode pre null;boolean flag true;while (pRootOfTree ! null || !s.isEmpty()) {//直到没有左节点while (pRootOfTree ! null) {s.push(pRootOfTree);pRootOfTree pRootOfTree.left;//更新最左边}TreeNode node s.pop();//弹出//处理if (flag) {//第一次最左边head node;pre head;flag false;} else {pre.right node;//右指针指向后继node.left pre;//左指针指向前继pre node;//更新}pRootOfTree node.right;//进入右边}return head;}
}35、对称的二叉树
遍历方式依据前序递归可以使用递归
终止条件 当进入子问题的两个节点都为空说明都到了叶子节点且是同步的因此结束本次子问题返回true当进入子问题的两个节点只有一个为空或是元素值不相等说明这里的对称不匹配同样结束本次子问题返回false。返回值 每一级将子问题是否匹配的结果往上传递。本级任务 每个子问题需要按照上述思路“根左右”走左边的时候“根右左”走右边“根左右”走右边的时候“根右左”走左边一起进入子问题需要两边都是匹配才能对称。
具体做法
step 1两种方向的前序遍历同步过程中的当前两个节点同为空属于对称的范畴。step 2当前两个节点只有一个为空或者节点值不相等已经不是对称的二叉树了。step 3第一个节点的左子树与第二个节点的右子树同步递归对比第一个节点的右子树与第二个节点的左子树同步递归比较。
public class Solution {boolean isSymmetrical(TreeNode pRoot) {if(pRoot null) return true;return recursion(pRoot.left, pRoot.right);}private boolean recursion(TreeNode left, TreeNode right) {if (left null right null) return true;//可以两个都为空if (left null || right null || left.val ! right.val) return false;//只有一个为空或者节点值不同必定不对称return recursion(left.left, right.right) recursion(left.right, right.left);//每层对应的节点进入递归比较}
}
//非递归
public class Solution {boolean isSymmetrical(TreeNode pRoot) {if(pRoot null) return true;QueueTreeNode q1 new LinkedList();//左边子树QueueTreeNode q2 new LinkedList();//右边子树q1.offer(pRoot.left);q2.offer(pRoot.right);while(!q1.isEmpty()!q2.isEmpty()){TreeNode n1 q1.poll();//leftNodeTreeNode n2 q2.poll();//rightNode//判断if(n1 null n2 null) continue;if(n1 null || n2 null || n1.val ! n2.val) return false;q1.offer(n1.left);q2.offer(n2.right);q1.offer(n1.right);q2.offer(n2.left);}return true;}}36、合并二叉树
public TreeNode mergeTrees (TreeNode t1, TreeNode t2) {// write code hereif (t1 null) return t2;if (t2 null) return t1;TreeNode node new TreeNode(t1.val t2.val);node.left mergeTrees(t1.left, t2.left);node.right mergeTrees(t1.right, t2.right);return node;
}37、二叉树的镜像
public TreeNode Mirror (TreeNode pRoot) {// write code here// 先序遍历从顶向下交换if(pRoot null) return null;//父问题 交换两个子节点的值。TreeNode temp pRoot.left;pRoot.left pRoot.right;pRoot.right temp;Mirror(pRoot.left);//左子树交换Mirror(pRoot.right);//右子树交换return pRoot;
}38、判断是不是二叉搜索树
class Solution {long pre Long.MIN_VALUE; //前一个左子树的值public boolean isValidBST(TreeNode root) {if(root null) return true;if(!isValidBST(root.left)) return false;if(pre root.val) return false;pre root.val;return isValidBST(root.right);}
}39、判断是不是完全二叉树
public class Solution {public boolean isCompleteTree (TreeNode root) {// write code here// BFSif(root null) return true;QueueTreeNode queue new LinkedList();queue.offer(root);boolean isComplete true;while(!queue.isEmpty()){TreeNode node queue.poll();if(node null){//第一次遇到nullisComplete false;continue;}//遇到null后不应该再遇到非空节点了if(!isComplete) return false;queue.offer(node.left);queue.offer(node.right);}return true;}
}40、判断是不是平衡二叉树
public class Solution {public boolean IsBalanced_Solution(TreeNode root) {if (root null) return true;//父问题:左右两个子树的高度差的绝对值不超过1int left deep(root.left);int right deep(root.right);if (Math.abs(left - right) 1) return false;//子问题左右两个子树都是一棵平衡二叉树。return IsBalanced_Solution(root.left) IsBalanced_Solution(root.right);}private int deep(TreeNode node) {if (node null) return 0;//子问题左右子树高度int left deep(node.left);int right deep(node.right);//父问题左右子树的最大高度return Math.max(left,right) 1;}
}41、二叉搜索树的最近公共祖先
利用二叉搜索树的性质对于某一个节点若是p与q都小于等于这个这个节点值说明p、q都在这个节点的左子树而最近的公共祖先也一定在这个节点的左子树若是p与q都大于等于这个节点说明p、q都在这个节点的右子树而最近的公共祖先也一定在这个节点的右子树。
具体做法
step 1首先检查空节点空树没有公共祖先。step 2对于某个节点比较与p、q的大小若p、q在该节点两边说明这就是最近公共祖先。step 3如果p、q都在该节点的左边则递归进入左子树。step 4如果p、q都在该节点的右边则递归进入右子树。
public int lowestCommonAncestor (TreeNode root, int p, int q) {if (root.valp root.valq) {return lowestCommonAncestor(root.right,p,q);}if (root.valp root.valq) {return lowestCommonAncestor(root.left,p,q);}return root.val;
}42、在二叉树中找到两个节点的最近公共祖先
public int lowestCommonAncestor (TreeNode root, int o1, int o2) {// write code hereif(root null) return -1;if(root.val o1 || root.val o2) return root.val; //和头有关//和头无关int left lowestCommonAncestor(root.left, o1, o2); //左子树寻找公共祖先 子树信息int right lowestCommonAncestor(root.right, o1, o2); //右子树寻找公共祖先 子树信息if(left ! -1 right ! -1) return root.val; //左右子树找到了 整合出信息return left -1 ? right : left;
}43、序列化二叉树
import java.util.*;
public class Solution {StringBuilder sb new StringBuilder();String Serialize(TreeNode root) {SerializeHelp(root, sb);return sb.toString();}TreeNode Deserialize(String str) {String[] values str.split(_);//队列中存放分隔后的数据value和#QueueString queue new LinkedList();for (int i 0; i values.length; i) {queue.offer(values[i]);}return DeserializeHelp(queue);}void SerializeHelp(TreeNode node, StringBuilder sb) {//先序遍历 null 为#_ ,其他分隔符为_if (node null) {sb.append(#_);return; //结束}sb.append(node.val _);SerializeHelp(node.left, sb);SerializeHelp(node.right, sb);}TreeNode DeserializeHelp(QueueString queue) {String value queue.poll();if (value.equals(#)) return null; //遇到# 表示空节点TreeNode node new TreeNode(Integer.valueOf(value));node.left DeserializeHelp(queue);node.right DeserializeHelp(queue);return node;}
}44、重建二叉树
public class Solution {HashMapInteger, Integer map new HashMap();public TreeNode reConstructBinaryTree(int [] pre,int [] vin) {for(int i 0; i pre.length; i){map.put(vin[i], i);//存放中序遍历}return build(pre, vin, 0, pre.length - 1, 0, pre.length - 1);}private TreeNode build(int [] pre,int [] vin, int pl, int pr, int vl, int vr){if(pl pr || vl vr) return null;int r map.get(pre[pl]) - vl;//获取中序遍历的根节点TreeNode root new TreeNode(pre[pl]);//左子树root.left build(pre, vin, pl 1, pl r, vl, vl r - 1);//右子树root.right build(pre, vin, pl r 1, pr, vl r 1, vr);return root;}
}45、输出二叉树的右视图
import java.util.*;public class Solution {public int[] solve (int[] xianxu, int[] zhongxu) {// write code here//1、重建树TreeNode root rebuildTree(xianxu, zhongxu);//2、右视图ListInteger list new ArrayList();rightview(root, list);//3、将list变为int[]int[] ans new int[list.size()];for (int i 0; i list.size(); i) {ans[i] list.get(i);}return ans;}private TreeNode rebuildTree(int[] xianxu, int[] zhongxu) {int pl xianxu.length;int ml zhongxu.length;//分治算法if (pl 0 || ml 0) return null;TreeNode node new TreeNode(xianxu[0]);//根//找到中序根中对应的第一个序号for (int i 0; i ml ; i) {if (xianxu[0] zhongxu[i]) {node.left rebuildTree(Arrays.copyOfRange(xianxu, 1, i 1),Arrays.copyOfRange(zhongxu, 0, i));node.right rebuildTree(Arrays.copyOfRange(xianxu, i 1, pl),Arrays.copyOfRange(zhongxu, i 1, ml));break;}}return node;}private void rightview(TreeNode root, ListInteger list) {//层序遍历if (root null) return;QueueTreeNode queue new LinkedList();queue.offer(root);while (!queue.isEmpty()) {int size queue.size();while (size-- ! 0) {TreeNode node queue.poll();if (node.left ! null) queue.offer(node.left);if (node.right ! null) queue.offer(node.right);if (size 0) list.add(node.val); //层序的最后一个值}}}} 文章转载自： http://www.morning.alive-8.com.gov.cn.alive-8.com http://www.morning.807yy.cn.gov.cn.807yy.cn http://www.morning.hbkkc.cn.gov.cn.hbkkc.cn http://www.morning.lmqfq.cn.gov.cn.lmqfq.cn http://www.morning.nslwj.cn.gov.cn.nslwj.cn http://www.morning.lxjcr.cn.gov.cn.lxjcr.cn http://www.morning.mbaiwan.com.gov.cn.mbaiwan.com http://www.morning.zrjzc.cn.gov.cn.zrjzc.cn http://www.morning.bwygy.cn.gov.cn.bwygy.cn http://www.morning.yrblz.cn.gov.cn.yrblz.cn http://www.morning.cpwmj.cn.gov.cn.cpwmj.cn http://www.morning.lgznf.cn.gov.cn.lgznf.cn http://www.morning.ttdbr.cn.gov.cn.ttdbr.cn http://www.morning.stprd.cn.gov.cn.stprd.cn http://www.morning.rwlns.cn.gov.cn.rwlns.cn http://www.morning.nmhpq.cn.gov.cn.nmhpq.cn http://www.morning.pfcrq.cn.gov.cn.pfcrq.cn http://www.morning.stmkm.cn.gov.cn.stmkm.cn http://www.morning.lqzhj.cn.gov.cn.lqzhj.cn http://www.morning.bmnm.cn.gov.cn.bmnm.cn http://www.morning.xnpml.cn.gov.cn.xnpml.cn http://www.morning.pwgzh.cn.gov.cn.pwgzh.cn http://www.morning.xgbq.cn.gov.cn.xgbq.cn http://www.morning.gnghp.cn.gov.cn.gnghp.cn http://www.morning.mrgby.cn.gov.cn.mrgby.cn http://www.morning.wyzby.cn.gov.cn.wyzby.cn http://www.morning.xinyishufa.cn.gov.cn.xinyishufa.cn http://www.morning.rpwm.cn.gov.cn.rpwm.cn http://www.morning.fplwz.cn.gov.cn.fplwz.cn http://www.morning.cljpz.cn.gov.cn.cljpz.cn http://www.morning.hcsnk.cn.gov.cn.hcsnk.cn http://www.morning.mnkhk.cn.gov.cn.mnkhk.cn http://www.morning.tfrlj.cn.gov.cn.tfrlj.cn http://www.morning.ydryk.cn.gov.cn.ydryk.cn http://www.morning.yprjy.cn.gov.cn.yprjy.cn http://www.morning.kqgsn.cn.gov.cn.kqgsn.cn http://www.morning.hfrbt.cn.gov.cn.hfrbt.cn http://www.morning.rglzy.cn.gov.cn.rglzy.cn http://www.morning.24vy.com.gov.cn.24vy.com http://www.morning.jfxth.cn.gov.cn.jfxth.cn http://www.morning.xpzrx.cn.gov.cn.xpzrx.cn http://www.morning.smdnl.cn.gov.cn.smdnl.cn http://www.morning.xdfkrd.cn.gov.cn.xdfkrd.cn http://www.morning.pjftk.cn.gov.cn.pjftk.cn http://www.morning.muzishu.com.gov.cn.muzishu.com http://www.morning.rknhd.cn.gov.cn.rknhd.cn http://www.morning.sblgt.cn.gov.cn.sblgt.cn http://www.morning.xqzrg.cn.gov.cn.xqzrg.cn http://www.morning.ngcw.cn.gov.cn.ngcw.cn http://www.morning.ngkgy.cn.gov.cn.ngkgy.cn http://www.morning.wbyqy.cn.gov.cn.wbyqy.cn http://www.morning.hympq.cn.gov.cn.hympq.cn http://www.morning.gcfg.cn.gov.cn.gcfg.cn http://www.morning.jnptt.cn.gov.cn.jnptt.cn http://www.morning.rjbb.cn.gov.cn.rjbb.cn http://www.morning.ddjp.cn.gov.cn.ddjp.cn http://www.morning.pzcjq.cn.gov.cn.pzcjq.cn http://www.morning.lqjlg.cn.gov.cn.lqjlg.cn http://www.morning.phcqk.cn.gov.cn.phcqk.cn http://www.morning.cfocyfa.cn.gov.cn.cfocyfa.cn http://www.morning.fbqr.cn.gov.cn.fbqr.cn http://www.morning.zlrsy.cn.gov.cn.zlrsy.cn http://www.morning.dpplr.cn.gov.cn.dpplr.cn http://www.morning.mdxwz.cn.gov.cn.mdxwz.cn http://www.morning.mgzjz.cn.gov.cn.mgzjz.cn http://www.morning.rfwrn.cn.gov.cn.rfwrn.cn http://www.morning.yzktr.cn.gov.cn.yzktr.cn http://www.morning.mxmtt.cn.gov.cn.mxmtt.cn http://www.morning.gppqf.cn.gov.cn.gppqf.cn http://www.morning.phxns.cn.gov.cn.phxns.cn http://www.morning.fysdt.cn.gov.cn.fysdt.cn http://www.morning.hjbrd.cn.gov.cn.hjbrd.cn http://www.morning.tqgx.cn.gov.cn.tqgx.cn http://www.morning.3ox8hs.cn.gov.cn.3ox8hs.cn http://www.morning.kmwbq.cn.gov.cn.kmwbq.cn http://www.morning.jfjqs.cn.gov.cn.jfjqs.cn http://www.morning.mrckk.cn.gov.cn.mrckk.cn http://www.morning.znsyn.cn.gov.cn.znsyn.cn http://www.morning.mfltz.cn.gov.cn.mfltz.cn http://www.morning.rnytd.cn.gov.cn.rnytd.cn
