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.順時針打印矩陣

題目描述
輸入一個矩陣死宣，按照從外向里以順時針的順序依次打印出每一個數(shù)字，例如碴开，如果輸入如下4 X 4矩陣： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 則依次打印出數(shù)字1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10.

思路1：
1.普通的循環(huán)打印毅该。把矩陣想象成若干個圈博秫。相當(dāng)于每次從（i,i）開始打印一整圈。
圈數(shù)應(yīng)該是 min(Math.ceil(row/2),Math.ceil(column/2))
2.對于每個圈眶掌，打印有四步挡育，圈可能并不完整，要判斷是否有必要進(jìn)行下一步打印即寒。
特別注意的是母赵，對于從右到左和從下到上的判斷凹嘲，不僅要判斷行施绎，還要判斷列谷醉。
思路2：
旋轉(zhuǎn)魔方俱尼。取出第一行萎攒，然后旋轉(zhuǎn)魔方耍休，重復(fù)上述操作羊精。需要額外的輔助空間喧锦，時間復(fù)雜度也較高。

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函數(shù)的棧

題目描述
定義棧的數(shù)據(jù)結(jié)構(gòu)，請在該類型中實現(xiàn)一個能夠得到棧中所含最小元素的min函數(shù)（時間復(fù)雜度應(yīng)為O（1））碍遍。
注意
1.必須滿足先進(jìn)先出雀久。才是一個棧
2.要求O（1）復(fù)雜度赖捌，所以不能每次排序
3.如果只存儲每次的最小值越庇，那么如果最小值出棧了师坎，勢必還要花費大于O（1）的時間復(fù)雜度去尋找新的最小值桑驱。
綜上熬的，需要采取一個輔助棧
思路
采用一個輔助棧。每次入棧時理逊，輔助棧入棧當(dāng)前最小值（min(新元素晋被，棧頂元素)）羡洛；出棧時翘县，輔助棧也一起出棧。保證輔助棧的棧頂元素就是當(dāng)前棧內(nèi)的最小值镀脂。輔助棧的含義類似于 加入當(dāng)前元素時薄翅，棧內(nèi)的最小值.
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.棧的壓入暑竟、彈出序列

題目描述
輸入兩個整數(shù)序列罗岖，第一個序列表示棧的壓入順序桑包，請判斷第二個序列是否可能為該棧的彈出順序。假設(shè)壓入棧的所有數(shù)字均不相等弱左。例如序列1,2,3,4,5是某棧的壓入順序科贬，序列4,5,3,2,1是該壓棧序列對應(yīng)的一個彈出序列榜掌，但4,3,5,1,2就不可能是該壓棧序列的彈出序列憎账。（注意：這兩個序列的長度是相等的）
思路
(不要看了胞皱，并不對)思路一：從規(guī)律上考慮反砌。如果序列遞增宴树，對于序列里面的所有數(shù)酒贬，如果前面的數(shù)字都大于或者都小于這個數(shù)锭吨，那么就是一個彈出序列零如。否則，則不是耸携≡玻可以用min,max記錄值河劝，然后比較。這里入棧的數(shù)字雖然不是遞增牌里，但是下標(biāo)是遞增的牡辽。我們可以用下標(biāo)值代替态辛。這里需要把出棧序列4,5,3,2,1轉(zhuǎn)化成它們的下標(biāo)對應(yīng)值序列奏黑；然后對轉(zhuǎn)化后的序列進(jìn)行判斷熟史。
這個思路不對！ｑ刹佟！
反例：pushA = {1,2,3,4,5};popA = {3,5,4,2,1};返回應(yīng)該是true吊骤；這里會變成false

正確思路：運用一個輔助棧白粉。對入棧序列依次入棧鸭巴，每次入棧時判斷棧頂元素是否是彈出序列中的當(dāng)前值，不是恬口，則不進(jìn)行出棧祖能，繼續(xù)入棧养铸；否則钞螟，出棧筛圆，接著判斷棧頂元素和彈出序列中的下一個值是否相等太援。
如果最后棧非空提岔，說明彈出序列不是該壓棧序列的彈出序列碱蒙。

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.從上到下打印二叉樹

題目描述
從上往下打印出二叉樹的每個節(jié)點，同層節(jié)點從左至右打印篮绰。
思路
其實就是層序遍歷吠各。廣度優(yōu)先遍歷也要使用隊列
使用LinkedList做隊列（實現(xiàn)了Deque方法）
ArrayList不適合做隊列，沒有實現(xiàn)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.二叉搜索樹的后序遍歷序列

題目描述
輸入一個整數(shù)數(shù)組，判斷該數(shù)組是不是某二叉搜索樹的后序遍歷的結(jié)果符匾。如果是則輸出Yes,否則輸出No叨咖。假設(shè)輸入的數(shù)組的任意兩個數(shù)字都互不相同。
思路
1.首先找規(guī)律：二叉搜索樹有：左<根<右啊胶；后序遍歷是左右根甸各。觀察一些遍歷序列，發(fā)現(xiàn) 根是序列的最后一個值焰坪。將前面的數(shù)組分為兩部分趣倾，一部分是左子樹節(jié)點儒恋；另一部分是右子樹節(jié)點
2.對于左右子樹炬守，也存在上述規(guī)律。所以可以使用遞歸來做。遞歸終止條件是，end<=start，這時表示沒有額外的節(jié)點需要再進(jìn)行判斷。所以返回true
3.如果前面的序列已經(jīng)有大于根的了，說明接下來都是右子樹節(jié)點。如果在接下來的序列里發(fā)現(xiàn)值小于根的八孝，說明不合題意楼入，返回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.二叉樹中和為某一值的路徑

題目描述
輸入一顆二叉樹的跟節(jié)點和一個整數(shù)府瞄，打印出二叉樹中結(jié)點值的和為輸入整數(shù)的所有路徑货邓。路徑定義為從樹的根結(jié)點開始往下一直到葉結(jié)點所經(jīng)過的結(jié)點形成一條路徑戈二。(注意: 在返回值的list中亏栈，數(shù)組長度大的數(shù)組靠前)
思路：
1.求路徑峻汉，是從根開始到葉節(jié)點阳懂。遍歷方式類似于前序遍歷（根左右）号枕，只不過艳狐，相對于前序遍歷，我們需要記錄下來遍歷的節(jié)點值近零。
2.最后返回的結(jié)果是一個ArrayList<ArrayList<Integer>>結(jié)構(gòu)裙士。里層裝的是各種可能路徑，且路徑排序方式是長路徑在前。
(怎么保證長路徑在前呢？目前的方法是先遍歷的子樹路徑在前睦刃，難道要每次遍歷前先算一下子樹大小再做么)
3.因為整數(shù)有正有負(fù)有零工育，所以只有遍歷到葉節(jié)點時，才知道這個路徑是不是符合題意肚吏。
4.首先就是要把當(dāng)前結(jié)點（首先是根結(jié)點）添加到路徑里，同時target 減去當(dāng)前結(jié)點的值任柜；然后宅粥，如果當(dāng)前結(jié)點為葉節(jié)點并且和也達(dá)到給定值环壤，就把這個路徑添加到列表，否則就一直遍歷下去；最后诈铛，遍歷到葉節(jié)點之后驶乾，返回上層結(jié)點之前，一定要把最后一個結(jié)點從路徑中刪除
5.遍歷完一個節(jié)點后循签，要返回到上個節(jié)點级乐，以便下次遍歷。

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);
        }
        //保證長數(shù)組先進(jìn)
        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);
    }
}

這樣時間復(fù)雜度要O(n^2)县匠。不知道有沒有更好的方式

8.復(fù)雜鏈表的復(fù)制

題目描述
輸入一個復(fù)雜鏈表（每個節(jié)點中有節(jié)點值风科，以及兩個指針，一個指向下一個節(jié)點聚唐，另一個特殊指針指向任意一個節(jié)點）丐重，返回結(jié)果為復(fù)制后復(fù)雜鏈表的head。（注意杆查，輸出結(jié)果中請不要返回參數(shù)中的節(jié)點引用扮惦，否則判題程序會直接返回空）
思路：
思路1：先按照next指針創(chuàng)建新鏈表；然后再遍歷亲桦，給random指針賦值崖蜜。賦值時需要找到對應(yīng)的指向節(jié)點位置，這里可以重頭遍歷原鏈表客峭，記錄步數(shù)s.豫领。然后在新鏈表中也需要走s步找到random指向的位置。時間復(fù)雜度O(n^2)
思路2：空間換時間舔琅。在第一次遍歷創(chuàng)建新鏈表的時候等恐，用一個hashmap記錄下<OldNode,NewNode>位置；然后賦值random的時候直接根據(jù)老節(jié)點找到新的節(jié)點备蚓。時間復(fù)雜度O(n)课蔬，空間復(fù)雜度O(n)
思路3：主要想法是如何快速定位新節(jié)點位置。我們把新節(jié)點串在老節(jié)點的后面郊尝。這樣二跋，random直接指向原來random節(jié)點的下一個位置。最后把兩個鏈表分離流昏。
分成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);
        
    }
    //第一步：復(fù)制節(jié)點。把新復(fù)制的節(jié)點接在原有節(jié)點后面况凉。
    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;
        }
    }
    //第二步：鏈接特殊指針谚鄙。原有節(jié)點指針指向S，那么復(fù)制節(jié)點的指針就指向S的下一個節(jié)點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 二叉搜索樹與雙向鏈表

題目描述
輸入一棵二叉搜索樹，將該二叉搜索樹轉(zhuǎn)換成一個排序的雙向鏈表膛锭。要求不能創(chuàng)建任何新的結(jié)點粮坞，只能調(diào)整樹中結(jié)點指針的指向。
思路：
看到排序聯(lián)想到中序遍歷初狰。二叉搜索樹的中序遍歷就是一個排序的數(shù)組莫杈。那么按照中序排序的思想，記錄下之前排完序的最后一個節(jié)點奢入，然后將這個節(jié)點和當(dāng)前節(jié)點連接筝闹，按順序依次連接，就能得到排序的雙向鏈表腥光。
注意
1.需要返回雙向鏈表的頭節(jié)點关顷。所以用一個全局變量指針leftNode，記錄頭節(jié)點（中序遍歷的第一個節(jié)點）
2.根節(jié)點和右子樹的最小節(jié)點的連接武福，其實是在遍歷右子樹最小節(jié)點時就做了议双。無需額外連接。（lastNode==root捉片，pRootOfTree==右子樹最小節(jié)點時平痰。）

/**
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.字符串的排列

題目描述
輸入一個字符串,按字典序打印出該字符串中字符的所有排列。例如輸入字符串a(chǎn)bc,則打印出由字符a,b,c所能排列出來的所有字符串a(chǎn)bc,acb,bac,bca,cab和cba伍纫。
輸入描述:
輸入一個字符串,長度不超過9(可能有字符重復(fù)),字符只包括大小寫字母宗雇。

思路：
遞歸做。字符串可看做兩部分：第一個字符和剩余的字符莹规。我們把第一個字符依次和后面的字符交換位置赔蒲，然后對剩余的n-1個字符進(jìn)行全排列。遞歸結(jié)束條件是良漱，剩余1個字符時舞虱。這時直接把相應(yīng)的char數(shù)組轉(zhuǎn)化成字符串存入list
注意：
1.要求按字典序返回。對結(jié)果進(jìn)行Collections.sort()
2.交換完债热，并且調(diào)用遞歸排列方法后砾嫉，還需要再交換回去。不然下一個位置的就亂了窒篱。
3.String.toCharArray()是String轉(zhuǎn)char[]焕刮。內(nèi)部調(diào)用arrayCopy生成新的char數(shù)組
new String(char[])和String.valueOf(char[])都是char轉(zhuǎn)String
4.由于可能存在重復(fù)字符，需要進(jìn)行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個字符構(gòu)成長度為1，2高镐，……溉旋，n的組合。當(dāng)求n個字符的長度為m的組合時嫉髓，我們把字符分成兩部分：當(dāng)前字符和剩余的n-1個字符观腊。這樣會出現(xiàn)兩種情況：一是m中包含當(dāng)前字符邑闲，則下一步在剩余的n-1個字符中選擇m-1個字符做組合；二是m中不包含當(dāng)前字符梧油，則下一步在剩余的n-1個字符中選擇m-1個字符做組合苫耸。所以問題轉(zhuǎn)化成，求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存入到結(jié)果集中
        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");
    }
}