1.单向反转链表

1.使用递归解决√

public ListNode reverseList(ListNode head) {
    //终止条件
    if (head == null || head.next == null)
        return head;
    //保存当前节点的下一个结点
    ListNode next = head.next;
    //从当前节点的下一个结点开始递归调用
    ListNode reverse = reverseList(next);
    /*reverse是反转之后的链表，因为函数reverseList
     表示的是对链表的反转，所以反转完之后next肯定
     是链表reverse的尾结点，然后我们再把当前节点*/
    //head挂到next节点的后面就完成了链表的反转。
    next.next = head;
    //这里head相当于变成了尾结点，尾结点都是为空的，
    //否则会构成环
    head.next = null;
    return reverse;
}
-------------------------------------------------------------
自己的想法:
    /**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        //定位到末结点
        if(head.next==null||head==null)
            return head;
        //3->4->5->1 假如当前head=node3,reverseList(head.next)=reverseList(node4)=node4=newHead
        ListNode newHead = reverseList(head.next);
        head.next.next = head;//即node4.next=node3
        head.next=null;//即node3.next=null 实现: node4->node3->null
        return newHead;
    }
}

2.尾递归*

public ListNode reverseList(ListNode head) {
    return reverseListInt(head, null);
}
private ListNode reverseListInt(ListNode head, ListNode newHead) {
    if (head == null)
        return newHead;
    ListNode next = head.next;
    head.next = newHead;
    return reverseListInt(next, head);
}

3.使用栈解决

class Solution {
   public ListNode reverseList(ListNode head) {
       Stack<ListNode> stack = new Stack<>();
       //将每个结点放入栈中
       while(head!=null){
           stack.push(head);
           head = head.next; 
       }
       //若栈为空，即没有结点，返回null
        if (stack.isEmpty())
        return null;
       //以第一个弹出的结点为头结点
       ListNode node = stack.pop();
       ListNode newHead = node;
       //依次弹栈接入头结点尾后
       while(!stack.isEmpty()){
           ListNode temp = stack.pop();
           node.next=temp;
           node = node.next;
       }
       //让尾结点的next为null
       node.next = null;
       return newHead;
   }
}

4.双链表求解

class Solution {
   public ListNode reverseList(ListNode head) {
       ListNode newHead = null;
       while(head!=null){
        //先保存访问的节点的下一个节点，保存起来留着下一步访问的
        ListNode temp = head.next;
        //每次访问的原链表节点都会成为新链表的头结点，其实就是把新链表挂到访问的原链表节点的后面就行了
        head.next = newHead;
        //更新新链表
        newHead = head;
        //重新赋值，继续访问
        head = temp;
       }
       return newHead;
   }
}
----------------------------------------------------------------
class Solution {
   public ListNode reverseList(ListNode head) {
       ListNode newHead = null;//1-2-3-4-5
       while(head!=null){
           ListNode temp = head.next;
           head.next=newHead;//核心 
           newHead=head;
           head=temp;
       }
       return newHead;
   }
}

2.链表内指定区间反转

import java.util.*;
/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 * }
 */
public class Solution {
    /**
     * 
     * @param head ListNode类 
     * @param m int整型 
     * @param n int整型 
     * @return ListNode类
     */
    public ListNode reverseBetween (ListNode head, int m, int n) {
             //设置虚拟头节点
        ListNode virHead = new ListNode(-1);
        virHead.next =head; //virHead.next=head
        ListNode pre = virHead;//pre = virHead 
        for(int i=1;i<m;i++){
            pre = pre.next;
        }//-1-1-2-3-4-5 m=2,n=4 ==>1-4-3-2-5 ==>pre=node1
        ListNode P1 = pre.next;//P1=node2
        ListNode P2;
        //双指针法
        for(int i=0;i<n-m;i++){//i<2,循环进行2次
            P2 = P1.next;//1:P2 = node3 2:P2 = node4
            P1.next = P2.next;//1:P1.next=node2.next=node4 2-4 2:node2.next=node4.next=node5 2-5
            P2.next = pre.next;//1:P2.next=node3.next=node2  3-2 2:node4.next=node2 4-3
            pre.next = P2; //1:node1.next=node3 1-3 2:node1.next=node4 1-4 
            //第一次循环:1-3(P2)-2(P1)-4-5  第二次循环:1-4-3-2-5
        }
        return virHead.next;
    }
}

TODO:建议画图重新温习一遍

3.链表中的节点每k个一组翻转

import java.util.*;
public class Solution {
    public ListNode reverseKGroup (ListNode head, int k) {
        if(k==1){
            return head;
        }
        int n,m=0;//①n为循环次数，m为链表总元素
        ListNode temp = head;
        while(temp!=null){
            temp=temp.next;
            m++;
        }
        n = m/k;
        ListNode virHead = new ListNode(-1);
        virHead.next=head;
        ListNode pre = virHead;
        for(int i=0;i<n;i++){ //②依次反转
//            if (pre.next==null){
//                break;
//            }这里用不着判断
            ListNode p1 = pre.next;
            ListNode p2;
            for(int j = 1; j < k;j++){//③双指针反转
                p2=p1.next;
                p1.next=p2.next;
                p2.next=pre.next;
                pre.next=p2;
            }
            pre=p1;//这一步很重要
        }
        return virHead.next;
    }
}

4.合并两个排序的链表

public class Solution {
    public ListNode Merge(ListNode list1,ListNode list2) {
        if (list1==null){
            return list2;
        }
        if (list2==null){
            return list1;
        }
        ListNode virHead = new ListNode(-1);
        ListNode temp = virHead;
        while(list1!=null&&list2!=null){
            if(list1.val<=list2.val){
                temp.next=list1;
                list1=list1.next;
            }else{
                temp.next=list2;
                list2=list2.next;
            }
            temp=temp.next;
        }
        temp.next=list1==null?list2:list1;
        return virHead.next;
    }
}

5.合并k个已排序的链表

树的基本算法

1.前序遍历

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 {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @return int整型一维数组
     */
    public int[] preorderTraversal (TreeNode root) {
        List<Integer> list = new ArrayList();
        preorder(root,list);
        int[] tree = new int[list.size()];
        for(int i=0;i<list.size();i++){
            tree[i]=list.get(i);
        }
        return tree;
    }
    public void preorder(TreeNode root,List list){
        if(root==null){
            return;
        }
        list.add(root.val);
        preorder(root.left,list);
        preorder(root.right,list);
    }
}

2.中序遍历

public class Solution {
    public int[] inorderTraversal (TreeNode root) {
        List<Integer> list = new ArrayList();
        inorder(root,list);
        int[] tree = new int[list.size()];
        for(int i = 0;i<list.size();i++){
            tree[i] = list.get(i); 
        }
        return tree;
    }
    public void inorder(TreeNode root,List list){
        if(root==null){
            return;
        }
        inorder(root.left,list);
        list.add(root.val);
        inorder(root.right,list);
    }
}

3.后序遍历

public class Solution {
    public int[] postorderTraversal (TreeNode root) {
        List<Integer> list = new ArrayList();
        postorder(list,root);
        int[] tree = new int[list.size()];
        for(int i = 0;i<list.size();i++){
            tree[i] = list.get(i);
        }
        return tree;
    }
    public void postorder(List list,TreeNode root){
        if(root==null){
            return;
        }
        postorder(list,root.left);
        postorder(list,root.right);
        list.add(root.val);
    }
}

4.层序遍历

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param root TreeNode类 
     * @return int整型ArrayList<ArrayList<>>
     */
    public ArrayList<ArrayList<Integer>> levelOrder (TreeNode root) {
        ArrayList<ArrayList<Integer>> res = new ArrayList();
        if(root == null){
            return res;
        }
        Queue<TreeNode> p = new ArrayDeque();
        p.add(root);
        System.out.println(p.size());
        while(!p.isEmpty()){
            ArrayList<Integer> r = new ArrayList();
            int n = p.size();
            for(int i = 0; i < n;i++){
                //int i = 0; i < p.size();i++这里有问题，不能用p.size()，必须要声明一个变量n
                //这是因为循环内部会使队列长度发生变化
                TreeNode temp = p.poll();
                r.add(temp.val);
                if(temp.left!=null){
                    p.add(temp.left);
                }
                if(temp.right!=null){
                    p.add(temp.right);
                }
            }
            res.add(r);
        }
        return res;
    }
}

5.树的深度

public int maxDepth (TreeNode root) {
        int rDepth = 0;
        int lDepth = 0;
        int Depth = 0;
        if(root == null){
            return 0;
        }
        lDepth = maxDepth(root.left);
        rDepth = maxDepth(root.right);
        Depth = lDepth>rDepth?lDepth+1:rDepth+1;
        return Depth;
}

6.按Z形顺序打印二叉树

import java.util.*;
public class Solution {
    public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
        TreeNode head = pRoot;
        ArrayList<ArrayList<Integer>> res = new ArrayList();
        if(pRoot==null){
            return res;
        }
        Queue<TreeNode> temp = new LinkedList();
        temp.offer(head);
        boolean flag = true;
        while(!temp.isEmpty()){
            ArrayList<Integer> list = new ArrayList();
            int n = temp.size();
            for(int i = 0; i< n;i++){
                TreeNode node = temp.poll();
                list.add(node.val);
                if(node.left!=null){
                    temp.offer(node.left);
                }
                if(node.right!=null){
                    temp.offer(node.right);
                }
            }
            //flag为真的时候不反转
            if(!flag){
                Collections.reverse(list);
            }
            res.add(list);
            flag = !flag;
        }
        return res;
    }
}

7.二叉树和为某一值的路径

import java.util.*;
public class Solution {
    public boolean hasPathSum (TreeNode root, int sum) {
        if(root == null){
            return false;
        }
        if(root.left==null&&root.right==null&&sum-root.val==0){
            return true;
        }
        return hasPathSum(root.left,sum-root.val) || hasPathSum(root.right,sum-root.val);
    }
}

8.二叉搜索树与双向链表的转化

import java.util.ArrayList;
import java.util.List;
public class Solution {
    public TreeNode Convert(TreeNode pRootOfTree) {
        if(pRootOfTree == null){
            return null;
        }
        ArrayList<TreeNode> list = new ArrayList<>();
        // 中序遍历
        Convert(list,pRootOfTree);
        // 构建双向链表
        return Convert(list);
    }
    public void Convert(ArrayList<TreeNode> list,TreeNode root){
        if(root != null){//这里的判断不能少，否则会报空指针异常
            Convert(list,root.left);
            list.add(root);
            Convert(list,root.right);
        }
    }

    /*
    这是核心代码，假设链表为 2 4 6 
    转化为双向链表为 2 <-> 4 <-> 6 
    */
    public TreeNode Convert(ArrayList<TreeNode> list){
        TreeNode head = list.get(0);
        TreeNode cur = head;
        for (int i=1;i< list.size();++i){
            TreeNode node=list.get(i);
            node.left=cur;
            cur.right=node;
            cur=node;
        }
        return head;
    }
}

9.判断二叉树是否对称

import java.util.*;
public class Solution {
    boolean isSymmetrical(TreeNode pRoot) {
        if(pRoot==null) return true;//判断根节点是否为空
        return isSymmetrical(pRoot.left,pRoot.right);
    }
    boolean isSymmetrical(TreeNode left,TreeNode right){
        if(left==null&&right==null) return true;
        if(left==null||right==null) return false;//左右结点一个有一个无
        //以下是两个结点都有的情况
        return left.val==right.val
            &&isSymmetrical(left.left,right.right)
            &&isSymmetrical(left.right,right.left);
    }
}

10.合并二叉树

import java.util.*;
public class Solution {
    public TreeNode mergeTrees (TreeNode t1, TreeNode t2) {
        //前序递归
        if(t1==null&&t2==null) return t1;
        if(t1==null||t2==null) return t1==null?t2:t1;
        t1.val=t1.val+t2.val;
        t1.left = mergeTrees(t1.left,t2.left);
        t1.right = mergeTrees(t1.right,t2.right);
        return t1;
    }
}

11.二叉树的镜像

import java.util.*;
public class Solution {
    public TreeNode Mirror (TreeNode pRoot) {
        if(pRoot==null) return pRoot;
        if(pRoot.left==null&&pRoot.right==null) return pRoot;//这里的作用在于少一次无意义的交换
        //前序递归
        TreeNode temp = pRoot.left;
        pRoot.left = pRoot.right;
        pRoot.right = temp;
        Mirror(pRoot.left);
        Mirror(pRoot.right);
        return pRoot;
    }
}

12.判断是否为二叉搜索树

import java.util.*;
public class Solution {
    public int min = Integer.MIN_VALUE;
    public boolean isValidBST (TreeNode root) {
        //一提到二叉搜索树，就要想到中序遍历
        if(root==null) return true;
        //递归左子树
        if(!isValidBST(root.left)) return false;
        //核心代码:如果min>当前节点值，则不是二叉搜索树，反之则将当前结点值赋值给min
        if(min>root.val){
            return false;
        }else{
            min = root.val;
        }
        //递归右子树
        if(!isValidBST(root.right)) return false;
        return true;
    }
}

13.判断是否为完全二叉树

import java.util.*;
public class Solution {
    public boolean isCompleteTree (TreeNode root) {
        if(root == null) return true;
        Queue<TreeNode> queue = new LinkedList();
        queue.add(root);
        boolean flag = true;
        while(!queue.isEmpty()){
            TreeNode temp = queue.poll();
            //很巧妙判断结点为null的下一个节点是否有值，若为null，continue，q为空退出循环
            //最终返回true，若不为null，执行if(flag==false)语句，最终返回false
            if(temp == null){
                flag = false;
                continue;
            }
            if(flag==false) return false;
            //如果是层序遍历，这里应该先判断左右结点是否为空，不为空才放入队列
            //而这里，加入最后一个节点后没有结点，也会放入两个null。
            //两个为null的情况，返回true；先有结点后为null的情况，返回true;先为null后有值才返回false
            queue.add(temp.left);
            queue.add(temp.right);
        }
        return true;
    }
}

14.判断是否为平衡二叉树

import java.util.*;
public class Solution {
    public boolean IsBalanced_Solution(TreeNode root) {
        if(root == null) return true;
        return Math.abs(Depth(root.right)-Depth(root.left))<=1&&
            IsBalanced_Solution(root.right)&&
            IsBalanced_Solution(root.left);
    }
    public int Depth(TreeNode node){
        //依然可以运用后续遍历的思想
        if(node == null) return 0;
        return Math.max(Depth(node.right),Depth(node.left))+1;
    }
}

15.二叉搜索树的最近公共祖先

import java.util.*;
public class Solution {
     public int lowestCommonAncestor (TreeNode root, int p, int q) {
         //两个都大于root结点，则向右递进
        if(root.val<p&&root.val<q){
            return lowestCommonAncestor(root.right,p,q);
        }
         //两个都小于root结点，则向左递进
         if(root.val>p&&root.val>q){
            return lowestCommonAncestor(root.left,p,q);
         }
         return root.val;
    }
}

16.在二叉树中找到两个节点的最近公共祖先

//稍微有点难想，建议画图思考
import java.util.*;
public class Solution {
    public int lowestCommonAncestor (TreeNode root, int o1, int o2) {
        return helper(root,o1,o2).val;
    }

    private TreeNode helper(TreeNode root,int p,int q){
        if(root==null) return root;
        if(root.val==p||root.val==q) return root;
        TreeNode left = helper(root.left,p,q);
        TreeNode right = helper(root.right,p,q);
        if(left==null) return right;
        if(right==null) return left;
        return root;
    }
}