涉及：二叉树，遍历，深度广度遍历，快排，冒泡，单链表
二叉树：
1.给你一个二叉树，要你打印输出所有路径。
https://blog.csdn.net/u014494703/article/details/50991031
二叉查找(搜索)树：左子树的值小于节点的值，右子树的值大于节点的值
中序遍历得到list，判断list是否是按顺序排列的
2.求二叉树的最大宽度和深度
深度用栈，宽度用队列，每次把下一层的节点放到队列里
https://www.cnblogs.com/xudong-bupt/p/4036190.html
https://www.cnblogs.com/xiaolovewei/p/7763867.html
3.前序中序后序遍历
根左右、左根右、左右根
public void getQianXu(TreeNode node){
System.out.println(node.getData());
if(node.getLeft()!=null){
getQianXu(node.getLeft());
}
if(node.getRight()!=null){
getQianXu(node.getRight());
}
}
4.二叉树节点数、二叉树叶子节点个数
public int getNodeCount(TreeNode root){
if(root==null){
return 0;
}else {
int leftLen=getNodeCount(root.getLeft());
int rightLen=getNodeCount(root.getRight());
return 1+leftLen+rightLen;
}
}
public int getChildNodeCount(TreeNode root){
if(root==null)
return 0;
if (root.getLeft()==null && root.getRight()==null){
return 1;
}else {
return getChildNodeCount(root.getLeft())+getChildNodeCount(root.getRight());
}
}
5.二叉树是否是平衡二叉树
public class Solution {
//后续遍历时，遍历到一个节点，其左右子树已经遍历 依次自底向上判断，每个节点只需要遍历一次
private boolean isBalanced=true;
public boolean IsBalanced_Solution(TreeNode root) {
getDepth(root);
return isBalanced;
}
public int getDepth(TreeNode root){
if(root==null)
return 0;
int left=getDepth(root.left);
int right=getDepth(root.right);
if(Math.abs(left-right)>1){
isBalanced=false;
}
return right>left ?right+1:left+1;
}
}
//广度遍历，使用队列，在每个元素弹出时，将他的子元素放到队列中
public List<Integer> getWidth(TreeNode root) {
List<Integer> list=new ArrayList<Integer>();
if(root==null){
return list;
}
Queue<TreeNode> queue=new LinkedList<TreeNode>();
queue.offer(root);
while (!queue.isEmpty()){
TreeNode node=queue.poll();
if(node.getLeft()!=null)
queue.offer(node.getLeft());
if(node.getRight()!=null)
queue.offer(node.getRight());
list.add(node.getData());
}
return list;
}
//深度遍历，用栈
public List<Integer> getDeep(TreeNode root) {
List<Integer> list=new ArrayList<Integer>();
if(root==null){
return list;
}
Stack<TreeNode> stack=new Stack<TreeNode>();
stack.push(root);
while (stack!=null){
TreeNode node=stack.pop();
if (node.getRight()!=null){
stack.push(node.getRight());
}
if(node.getLeft()!=null){
stack.push(node.getLeft());
}
list.add(node.getData());
}
return list;
}
单链表
1.求两个链表是否相交，求两个链表相交于哪个节点
https://blog.csdn.net/qq_39435120/article/details/79741241
https://www.jianshu.com/p/634c147fe2a9
https://blog.csdn.net/linyousong/article/details/50759869
2.单链表反转
https://www.cnblogs.com/zhengcj/p/7494089.html
遍历
String str1="abdcdefghidefmnabc";
String str2="def";
for(int i=0;i<str1.length()-str2.length();i++){
if(str1.substring(i,i+str2.length()).equals(str2)){
System.out.println("you"+i);
}
}
排序
（1）冒泡O(n*2)：
思想：把第一个值与后边的值进行比较，如果第一个值比后边的大，交换位置，这样一轮下来最大的值就到了最后，依次执行。（把最大的值放到后边）
https://blog.csdn.net/u010853261/article/details/54891710
for(int i=0;i<arr.length-1;i++){
for(int j=0;j<arr.length-1-i;j++){
if(arr[j]>arr[j+1]){
int temp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=temp;
}
}
}
（2）选择排序O(n*2)：
思想：选定第一个值，后边选出最小的值，如果最小的值比当前值还小，交换，这样最小的值就慢慢到了前边（第一轮选最小的，第二轮选次小的。。。）（把最小的值放到前边）
public static void chooseSort(int[] arr){
for(int i=0;i<arr.length-1;i++){
int mixIndex=i;
for(int j=i+1;j<arr.length;j++){
if(arr[j]<arr[mixIndex]){
mixIndex=j;
}
}
int temp=arr[i];
arr[i]=arr[mixIndex];
arr[mixIndex]=temp;
}
}
（3）快排
https://www.cnblogs.com/hjy9420/p/5032309.html
快速排序的原理：选择一个关键值作为基准值。比基准值小的都在左边序列（一般是无序的），比基准值大的都在右边（一般是无序的）。一般选择序列的第一个元素。
public void sort(int[] arr,int low,int high){
int start = low;
int end = high;
int key = arr[low];
while(end>start){
//从后往前比较
while(end>start&&arr[end]>=key) //如果没有比关键值小的，比较下一个，直到有比关键值小的交换位置，然后又从前往后比较
end--;
if(arr[end]<=key){
int temp = arr[end];
arr[end] = arr[start];
arr[start] = temp;
}
//从前往后比较
while(end>start&&arr[start]<=key)//如果没有比关键值大的，比较下一个，直到有比关键值大的交换位置
start++;
if(arr[start]>=key){
int temp = arr[start];
arr[start] = arr[end];
arr[end] = temp;
}
//此时第一次循环比较结束，关键值的位置已经确定了。左边的值都比关键值小，右边的值都比关键值大，但是两边的顺序还有可能是不一样的，进行下面的递归调用
}
//递归
if(start>low) sort(arr,low,start-1);//左边序列。第一个索引位置到关键值索引-1
if(end<high) sort(arr,end+1,high);//右边序列。从关键值索引+1到最后一个
}
（4）插入排序
https://www.cnblogs.com/bjh1117/p/8335628.html
思想：选定index=1往后的位置，假定左边都是有序的，要是左边的元素比当前值大，移到该值的右边，最后把该值放到空出来的位置。
public void doInsertSort(){
for(int index = 1; index<length; index++){//外层向右的index，即作为比较对象的数据的index
int temp = array[index];//用作比较的数据
int leftindex = index-1;
while(leftindex>=0 && array[leftindex]>temp){//当比到最左边或者遇到比temp小的数据时，结束循环
array[leftindex+1] = array[leftindex];
leftindex--;
}
array[leftindex+1] = temp;//把temp放到空位上
}
}
- 二分法查找（[5,2,1,6,8,7,3]）
https://blog.csdn.net/android_for_james/article/details/51492493
public static int rank(int key,int nums[])
{
//查找范围的上下界
int low=0;
int high=nums.length-1;
//未查找到的返回值
int notFind=-1;
while(low<=high)
{
//二分中点=数组左边界+(右边界-左边界)/2
//整数类型默认取下整
int mid=low+(high-low)/2;
//中间值是如果大于key
if(nums[mid]>key)
{
//证明key在[low,mid-1]这个区间
//因为num[mid]已经判断过了所以下界要减一
high=mid-1;
}else if(nums[mid]<key)
{
//证明key在[mid+1,high]这个区间
//同样判断过mid对应的值要从mid+1往后判断
low=mid+1;
}
else
{
//查找成功
return mid;
}
}
//未成功
return notFind;
}
