1.镜像二叉树

题目描述
操作给定的二叉树，将其变换为源二叉树的镜像。
输入描述:
二叉树的镜像定义：源二叉树
8
/ \
6 10
/ \ / \
5 7 9 11
镜像二叉树
8
/ \
10 6
/ \ / \
11 9 7 5

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

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution {
    public void Mirror(TreeNode root) {
        if(root==null)return;
        TreeNode temp = root.left;
        root.left=root.right;
        root.right=temp;
        Mirror(root.left);
        Mirror(root.right);
    }
}

2.顺时针打印矩阵

题目描述
输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，如果输入如下4 X 4矩阵： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 则依次打印出数字1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10.

思路1：
1.普通的循环打印。把矩阵想象成若干个圈。相当于每次从（i,i）开始打印一整圈。
圈数应该是 min(Math.ceil(row/2),Math.ceil(column/2))
2.对于每个圈，打印有四步，圈可能并不完整，要判断是否有必要进行下一步打印。
特别注意的是，对于从右到左和从下到上的判断，不仅要判断行，还要判断列。
思路2：
旋转魔方。取出第一行，然后旋转魔方，重复上述操作。需要额外的辅助空间，时间复杂度也较高。

import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> printMatrix(int [][] matrix) {
        ArrayList<Integer> list = new ArrayList<Integer>();
        if(matrix.length==0||matrix[0].length==0)return list;
        int row = matrix.length;
        int column = matrix[0].length;
        int start = 0;
        while((start*2<row)&&(start*2<column)){
            printCircleMatrix(matrix,start,list);
            start++;
        }
        return list;
    }
    public void printCircleMatrix(int[][] matrix,int start,ArrayList<Integer> list){
        int row = matrix.length;
        int column = matrix[0].length;
        int endX = column-start-1;
        int endY = row-start-1;
        for(int j = start;j<=endX;j++){
            list.add(matrix[start][j]);
        }
        if(endY>start){
            for(int i= start+1;i<=endY;i++){
                list.add(matrix[i][endX]);
            }
        }
        if(endX>start && endY>start){
            for(int j = endX-1;j>=start;j--){
                list.add(matrix[endY][j]);
            }
        }
        if(endY>start+1 && endX>start){
            for(int i = endY-1;i>=start+1;i--){
                list.add(matrix[i][start]);
            }
        }
    }
}

3.包含min函数的栈

题目描述
定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。
注意
1.必须满足先进先出。才是一个栈
2.要求O（1）复杂度，所以不能每次排序
3.如果只存储每次的最小值，那么如果最小值出栈了，势必还要花费大于O（1）的时间复杂度去寻找新的最小值。
综上，需要采取一个辅助栈
思路
采用一个辅助栈。每次入栈时，辅助栈入栈当前最小值（min(新元素，栈顶元素)）；出栈时，辅助栈也一起出栈。保证辅助栈的栈顶元素就是当前栈内的最小值。辅助栈的含义类似于 加入当前元素时，栈内的最小值.
top/min时如果栈为空，这里会打印异常，并且返回-1值作为异常值（可能不太好）

import java.util.Stack;

public class Solution {

    Stack<Integer> stack = new Stack<Integer>();
    Stack<Integer> minStack = new Stack<Integer>();
    public void push(int node) {
        stack.push(node);
        if(minStack.empty()||node<minStack.peek()){
            minStack.push(node);
        }else{
            minStack.push(minStack.peek());
        }
    }
    
    public void pop() {
        stack.pop();
        minStack.pop();
    }
    
    public int top() {
        if(stack.empty()){
            System.out.println("stack为空");
            return -1;
        }
        return stack.peek();
    }
    
    public int min() {
        if(minStack.empty()){
            System.out.println("stack为空");
            return -1;
        }
        return minStack.peek();
    }
}

4.栈的压入、弹出序列

题目描述
输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）
思路
(不要看了，并不对)思路一：从规律上考虑。如果序列递增，对于序列里面的所有数，如果前面的数字都大于或者都小于这个数，那么就是一个弹出序列。否则，则不是。可以用min,max记录值，然后比较。这里入栈的数字虽然不是递增，但是下标是递增的。我们可以用下标值代替。这里需要把出栈序列4,5,3,2,1转化成它们的下标对应值序列；然后对转化后的序列进行判断。
这个思路不对！！！
反例：pushA = {1,2,3,4,5};popA = {3,5,4,2,1};返回应该是true；这里会变成false

正确思路：运用一个辅助栈。对入栈序列依次入栈，每次入栈时判断栈顶元素是否是弹出序列中的当前值，不是，则不进行出栈，继续入栈；否则，出栈，接着判断栈顶元素和弹出序列中的下一个值是否相等。
如果最后栈非空，说明弹出序列不是该压栈序列的弹出序列。

import java.util.ArrayList;
import java.util.Stack;

public class Solution {
    public boolean IsPopOrder(int [] pushA,int [] popA) {
        if(pushA==null&&popA==null||pushA.length==0&&popA.length==0)return true;
        if(pushA==null||popA==null||pushA.length==0||popA.length==0)return false;
        Stack<Integer> stack = new Stack<Integer>();
        int j=0;
        for(int i=0;i<pushA.length;i++){
            stack.push(pushA[i]);
            while((j<popA.length)&&stack.peek()==popA[j]){
                stack.pop();
                j++;
            }
        }
        return stack.empty();
    }
}

5.从上到下打印二叉树

题目描述
从上往下打印出二叉树的每个节点，同层节点从左至右打印。
思路
其实就是层序遍历。广度优先遍历也要使用队列
使用LinkedList做队列（实现了Deque方法）
ArrayList不适合做队列，没有实现Deque接口，没有上述提及的pop,poll,peek,offer这些方法。只有add和remove(index)。

import java.util.ArrayList;
import java.util.LinkedList;
/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution {
    public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
        ArrayList<Integer> result = new ArrayList<Integer>();
        LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
        if(root==null)return result;
        queue.offer(root);
        while(!queue.isEmpty()){
            TreeNode temp = queue.poll();
            result.add(temp.val);
            if(temp.left!=null){
                queue.offer(temp.left);
            }
            if(temp.right!=null){
                queue.offer(temp.right);
            }
        }
        return result;   
    }
}

6.二叉搜索树的后序遍历序列

题目描述
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。
思路
1.首先找规律：二叉搜索树有：左<根<右；后序遍历是左右根。观察一些遍历序列，发现 根是序列的最后一个值。将前面的数组分为两部分，一部分是左子树节点；另一部分是右子树节点
2.对于左右子树，也存在上述规律。所以可以使用递归来做。递归终止条件是，end<=start，这时表示没有额外的节点需要再进行判断。所以返回true
3.如果前面的序列已经有大于根的了，说明接下来都是右子树节点。如果在接下来的序列里发现值小于根的，说明不合题意，返回false
如果输入的序列为空或null时，不是二叉搜索树的后序遍历

public class Solution {
    public boolean VerifySquenceOfBST(int [] sequence) {
        if(sequence ==null||sequence.length==0)return false;
        return verifyCircle(sequence,0,sequence.length-1);
    }
    public boolean verifyCircle(int[] sub,int start,int end){
        if(end-start<=0){
           return true; 
        }
        int root = sub[end];
        int leftCount =0;
        boolean rightflag=false;
        for(int i=start;i<end;i++){
            if(sub[i]<root&&!rightflag){
                leftCount++;
            }else if(sub[i]<root&&rightflag){
                return false;
            }else if(sub[i]>root){
                rightflag=true;
            }
        }
        return verifyCircle(sub,start,leftCount-1)&&verifyCircle(sub,leftCount,end-1);
    }
}

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

题目描述
输入一颗二叉树的跟节点和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。(注意: 在返回值的list中，数组长度大的数组靠前)
思路：
1.求路径，是从根开始到叶节点。遍历方式类似于前序遍历（根左右），只不过，相对于前序遍历，我们需要记录下来遍历的节点值。
2.最后返回的结果是一个ArrayList<ArrayList<Integer>>结构。里层装的是各种可能路径，且路径排序方式是长路径在前。
(怎么保证长路径在前呢？目前的方法是先遍历的子树路径在前，难道要每次遍历前先算一下子树大小再做么)
3.因为整数有正有负有零，所以只有遍历到叶节点时，才知道这个路径是不是符合题意。
4.首先就是要把当前结点（首先是根结点）添加到路径里，同时target 减去当前结点的值；然后，如果当前结点为叶节点并且和也达到给定值，就把这个路径添加到列表，否则就一直遍历下去；最后，遍历到叶节点之后，返回上层结点之前，一定要把最后一个结点从路径中删除
5.遍历完一个节点后，要返回到上个节点，以便下次遍历。

import java.util.ArrayList;
/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution {
    ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
    ArrayList<Integer> path = new ArrayList<Integer>();
    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
        if(root==null)return result;
        path.add(root.val);
        int currentTarget = target-root.val;
        if(currentTarget==0&&root.left==null&&root.right==null){
            ArrayList<Integer> temp = new ArrayList<Integer>(path);
            result.add(temp);
        }
        //保证长数组先进
        if(HeightOfTree(root.left)>=HeightOfTree(root.right)){
            FindPath(root.left,currentTarget);
            FindPath(root.right,currentTarget);
        }else{
            FindPath(root.right,currentTarget);
            FindPath(root.left,currentTarget);
        }
        path.remove(path.size()-1);
        return result;
    }
    public int HeightOfTree(TreeNode node){
        if(node==null)return 0;
        return Math.max(HeightOfTree(node.left)+1,HeightOfTree(node.right)+1);
    }
}

这样时间复杂度要O(n^2)。不知道有没有更好的方式

8.复杂链表的复制

题目描述
输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）
思路：
思路1：先按照next指针创建新链表；然后再遍历，给random指针赋值。赋值时需要找到对应的指向节点位置，这里可以重头遍历原链表，记录步数s.。然后在新链表中也需要走s步找到random指向的位置。时间复杂度O(n^2)
思路2：空间换时间。在第一次遍历创建新链表的时候，用一个hashmap记录下<OldNode,NewNode>位置；然后赋值random的时候直接根据老节点找到新的节点。时间复杂度O(n)，空间复杂度O(n)
思路3：主要想法是如何快速定位新节点位置。我们把新节点串在老节点的后面。这样，random直接指向原来random节点的下一个位置。最后把两个链表分离。
分成3步做。

961875_1469289666488_886555C4C4726220976FEF4D3A32FFCD.png

/*
public class RandomListNode {
    int label;
    RandomListNode next = null;
    RandomListNode random = null;

    RandomListNode(int label) {
        this.label = label;
    }
}
*/
public class Solution {
    public RandomListNode Clone(RandomListNode pHead)
    {
        if(pHead==null)return null;
        cloneNodes(pHead);
        connectedRandom(pHead);
        return splitRandomList(pHead);
        
    }
    //第一步：复制节点。把新复制的节点接在原有节点后面。
    public void cloneNodes(RandomListNode pHead){
        RandomListNode temp=pHead;
        while(temp!=null){
            RandomListNode next = temp.next;
            RandomListNode newNode = new RandomListNode(temp.label);
            temp.next = newNode;
            newNode.next = next;
            temp = next;
        }
    }
    //第二步：链接特殊指针。原有节点指针指向S，那么复制节点的指针就指向S的下一个节点S'
    public void connectedRandom(RandomListNode pHead){
        RandomListNode temp=pHead;
        while(temp!=null){
            RandomListNode newNode = temp.next;
            RandomListNode randomNode = temp.random;
            //newNode.random = randomNode.next;（如果不按下面写，会抛NPE）
            newNode.random = randomNode==null?null:randomNode.next;
            temp = newNode.next;
        }
    }
    //第三部：分开两个链表。
    public RandomListNode splitRandomList(RandomListNode head){
        RandomListNode newRandomHead = null;
        RandomListNode newtemp=null;
        RandomListNode temp = head;
        if(temp!=null){
            newRandomHead = temp.next;
            newtemp = temp.next;
            if(newtemp==null)return newRandomHead;
            temp.next = newtemp.next; 
            temp = temp.next;
        }
        while(temp!=null){
            newtemp.next = temp.next;
            newtemp = newtemp.next;
            if(newtemp==null)return newRandomHead;
            temp.next = newtemp.next; 
            temp = temp.next;
        }
        return newRandomHead;
    }
}

9 二叉搜索树与双向链表

题目描述
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。
思路：
看到排序联想到中序遍历。二叉搜索树的中序遍历就是一个排序的数组。那么按照中序排序的思想，记录下之前排完序的最后一个节点，然后将这个节点和当前节点连接，按顺序依次连接，就能得到排序的双向链表。
注意
1.需要返回双向链表的头节点。所以用一个全局变量指针leftNode，记录头节点（中序遍历的第一个节点）
2.根节点和右子树的最小节点的连接，其实是在遍历右子树最小节点时就做了。无需额外连接。（lastNode==root，pRootOfTree==右子树最小节点时。）

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

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution {
    TreeNode leftNode = null;
    TreeNode lastNode = null;
    public TreeNode Convert(TreeNode pRootOfTree) {
        if(pRootOfTree==null)return leftNode;
        Convert(pRootOfTree.left);
        if(leftNode==null){
            leftNode=pRootOfTree;
            lastNode=pRootOfTree;
        }else{
            lastNode.right = pRootOfTree;
            pRootOfTree.left = lastNode;
            lastNode=pRootOfTree;
        }
        Convert(pRootOfTree.right);
        return leftNode;
    }
}

10.字符串的排列

题目描述
输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
输入描述:
输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。

思路：
递归做。字符串可看做两部分：第一个字符和剩余的字符。我们把第一个字符依次和后面的字符交换位置，然后对剩余的n-1个字符进行全排列。递归结束条件是，剩余1个字符时。这时直接把相应的char数组转化成字符串存入list
注意：
1.要求按字典序返回。对结果进行Collections.sort()
2.交换完，并且调用递归排列方法后，还需要再交换回去。不然下一个位置的就乱了。
3.String.toCharArray()是String转char[]。内部调用arrayCopy生成新的char数组
new String(char[])和String.valueOf(char[])都是char转String
4.由于可能存在重复字符，需要进行contains判断。去重

import java.util.ArrayList;
import java.util.Collections;
public class Solution {
    ArrayList<String> list = new ArrayList<String>();
    public ArrayList<String> Permutation(String str) {
        if(str.isEmpty()){
            return list;
        }
        char[] array = str.toCharArray();
        PermutationHelper(array,0);
        Collections.sort(list);
        return list;
    }
    public void PermutationHelper(char[] array,int start){
        if(start==array.length-1){
            String val = String.valueOf(array);
            if(!list.contains(val)){
                list.add(val);
            }
            return;
        }
        for(int i=start;i<array.length;i++){
            swap(array,start,i);
            PermutationHelper(array,start+1);
            swap(array,start,i);
        }
    }
    public void swap(char[] array,int i,int j){
        char temp = array[i];
        array[i]=array[j];
        array[j]=temp;
    }
}

题目变种：求字符的所有组合
思路：如果输入n个字符，则这n个字符构成长度为1，2，……，n的组合。当求n个字符的长度为m的组合时，我们把字符分成两部分：当前字符和剩余的n-1个字符。这样会出现两种情况：一是m中包含当前字符，则下一步在剩余的n-1个字符中选择m-1个字符做组合；二是m中不包含当前字符，则下一步在剩余的n-1个字符中选择m-1个字符做组合。所以问题转化成，求n个字符的1，2，3，……，n个长度的组合；而在求这些组合的时候可以采取递归来做，递归的终止条件是m==0（这时可以把组合加入）或者没有需要用来添加的字符（这时尝试失败）

import java.util.ArrayList;
public class Solution {
    ArrayList<String> list = new ArrayList<String>();
    public ArrayList<String> Permutation(String str) {
        if(str.isEmpty()){
            return list;
        }
        //用来存放一个组合串
        StringBuilder sb = new StringBuilder();
        for(int i=1;i<=str.length();i++){
            PermutationHelper(str,0,i,sb);
        }
        return list;
    }
    public void PermutationHelper(String s,int start,int m,StringBuilder sb){
        //终止条件1：取0个字符串，这时可以把之前的sb存入到结果集中
        if(m==0){
            if(!list.contains(sb.toString())){
                list.add(sb.toString());
            }
            return;
        }
        //终止条件2：没有可以用来添加的字符了：说明这个组合不合适
        if(start==s.length()){
            return;
        }
        //情况1：m个字符中包含Start位置的字符，剩余的字符中取m-1个
        sb.append(s.charAt(start));
        PermutationHelper(s,start+1,m-1,sb);
        //情况2：m个字符中不包含Start位置的字符（把之前添加的去掉），剩余的字符中取m个
        sb.deleteCharAt(sb.length()-1);
        PermutationHelper(s,start+1,m,sb);
    }
    public static void main(String[] args){
        Solution su = new Solution();
        ArrayList<String> list = su.Permutation("abc");
    }
}