使二叉樹變?yōu)槠溏R像
類似先序遍歷的方法

    public void mirror(TreeNode node){
        if(node==null)
            return;
        if(node.left==null&&node.right==null)
            return;
        TreeNode n=node.left;
        node.left=node.right;
        node.right=n;
        mirror(node.left);
        mirror(node.right);
    }

判斷二叉樹是否對稱
左節(jié)點(diǎn)的右子樹和右節(jié)點(diǎn)的左子樹相同 使用遞歸

    boolean isSymmetrical(TreeNode pRoot){
        if(pRoot==null)
            return true;
        return comRoot(pRoot.left,pRoot.right);
    }
    
    boolean comRoot(TreeNode left,TreeNode right){
        if(left==null)
            return right==null;
        if(right==null)
            return false;
        if(left.val!=right.val)
            return false;
        return comRoot(left.right, right.left)&&comRoot(left.left, right.right);
    }

實(shí)現(xiàn)有Min函數(shù)的棧

    Stack<Integer> stack1=new Stack<>();
    Stack<Integer> stack2=new Stack<>();
    public void push(int node) {
        stack1.push(node);
        if(stack2.isEmpty())
            stack2.push(node);
        else{
            if(node<stack2.peek())
                stack2.push(node);
            else
                stack2.push(stack2.peek());
        }
    }
    
    public void pop() {
        stack1.pop();
        stack2.pop();
    }
    
    public int top() {
       return  stack1.peek();
    }
    
    public int min() {
        return stack2.peek();
    }

給出入棧順序，判斷出棧順序是否正確

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

判斷是否是二叉搜索樹的后序遍歷序列

  public boolean judge(int[] a,int start,int end){
        if(start>=end)
            return true;
        int i=start;
        while(i<end&&a[i]<a[end]){
            i++;
        }
        for(int j=i;j<end;j++){
            if(a[j]<a[end])
                return false;
        }
        return judge(a,start,i-1)&&judge(a,i,end-1);
    }

尋找二叉樹從根到葉子值為x的路徑

//方法一 使用棧
    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
       ArrayList<ArrayList<Integer>> all=new ArrayList<ArrayList<Integer>>();
       if(root==null)
           return all;
       Stack<Integer> stack=new Stack<Integer>();
       FindPath(root, target,stack,all);
       return all;
    }
    

    
    void FindPath(TreeNode root,int target,Stack<Integer> stack, ArrayList<ArrayList<Integer>> all){
        if(root==null)
            return;
        if(root.left==null&&root.right==null){
            if(root.val==target){
                ArrayList<Integer> list=new ArrayList<>();
                for(int i:stack){
                    list.add(new Integer(i));
                }
                list.add(new Integer(root.val));
                all.add(list);
            }
        }else{
            stack.push(new Integer(root.val));
            FindPath(root.left,target-root.val,stack,all);
            FindPath(root.right, target-root.val, stack, all);
            stack.pop();
        }
    }

//方法二
  public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
            if(root==null)
                return listAll;
            list.add(root.val);
            target-=root.val;
            if(target==0&&root.left==null&&root.right==null)
                listAll.add(new ArrayList<Integer>(list));
            FindPath(root.left,target);
            FindPath(root.right, target);
            list.remove(list.size()-1);
            return listAll;
        }

求字符串全排列結(jié)果 按字典順序返回
劃分為子問題 第一個數(shù)和后面每個數(shù)交換 第二個數(shù)和后面每個數(shù)交換 ...

    public ArrayList<String>  Permutation(String str) {
        char []c=str.toCharArray();
        ArrayList<String> list=new ArrayList<>();
        if(str!=null&&str.length()>0){
            permutation(c,0,list);
            Collections.sort(list);
        }
        for(String i:list)
            System.out.println(i);
        return list;
    }
    
    void permutation(char[] c,int start,ArrayList<String> list){
        if(start==c.length-1){
            //System.out.println(Arrays.toString(c));
            String s=String.valueOf(c);
            if(!list.contains(s))
                list.add(s);
        }
        for(int i=start;i<c.length;i++){
            char temp=c[start];
            c[start]=c[i];
            c[i]=temp;
            permutation(c,start+1,list);
            temp=c[start];
            c[start]=c[i];
            c[i]=temp;
        }
    }

克隆復(fù)雜鏈表 該鏈表兩個指針 一個指向下一個 一個隨機(jī)指向
思路：
第一步：根據(jù)原始鏈表每個節(jié)點(diǎn)N創(chuàng)建對應(yīng)的N'，把N'鏈接到N后面
第二步：根據(jù)原始鏈表每個節(jié)點(diǎn)N的random指針，設(shè)置新節(jié)點(diǎn)的random指針，為原指針的下一位
第三步：將第二步得到的鏈表拆分，奇數(shù)位置是原始鏈表，偶數(shù)位置是復(fù)制出來的鏈表 實(shí)現(xiàn)過程的一些細(xì)節(jié)要注意

//根據(jù)原始鏈表每個節(jié)點(diǎn)N創(chuàng)建對應(yīng)的N'，把N'鏈接到N后面
    void clonenodes(RandomListNode phead){
        RandomListNode pnode=phead;
        while(pnode!=null){
            RandomListNode pcloned=new RandomListNode(-1);
            pcloned.label=pnode.label;
            pcloned.next=pnode.next;
            pcloned.random=null;
            pnode.next=pcloned;
            pnode=pcloned.next;
        }
    }
//根據(jù)原始鏈表每個節(jié)點(diǎn)N的random指針，設(shè)置新節(jié)點(diǎn)的random指針，為原指針的下一位  
    void connectrandom(RandomListNode phead){
        RandomListNode pnode=phead;
        while(pnode!=null){
            RandomListNode pcloned=pnode.next;
            if(pnode.random!=null){
                pcloned.random=pnode.random.next;
            }
            pnode=pcloned.next;
        }
    }
    
    RandomListNode reconnect(RandomListNode phead){
        RandomListNode pnode=phead;
        RandomListNode pclonedHead=null;
        RandomListNode pclonedNode=null;
        if(pnode!=null){
            pclonedHead=pclonedNode=pnode.next;
            pnode.next=pclonedNode.next;
            pnode=pnode.next;
        }
        
        while(pnode!=null){
            pclonedNode.next=pnode.next;
            pclonedNode=pclonedNode.next;
            pnode.next=pclonedNode.next;
            pnode=pnode.next;
        }
        return pclonedHead;
    }
    
    RandomListNode clone(RandomListNode node){
        clonenodes(node);
        connectrandom(node);
        return reconnect(node);
    }

class RandomListNode {
    int label;
    RandomListNode next = null;
    RandomListNode random = null;

    RandomListNode(int label) {
        this.label = label;
    }
}

//O（1）時間刪除鏈表非尾節(jié)點(diǎn)的節(jié)點(diǎn)
將下一個節(jié)點(diǎn)的值復(fù)制給該節(jié)點(diǎn)，刪除下一個節(jié)點(diǎn)，調(diào)整鏈接。

    void delete(ListNode p,ListNode del){
        if(p==null||del==null)
            return;
        if(del.next!=null){
            del.val=del.next.val;
            del.next=del.next.next;
        }else if(p==del){
            p=null;
        }else{
            ListNode pnode=p;
            while(pnode.next!=del)
                pnode=pnode.next;
            pnode.next=null;
        }
    }

順時針打印矩陣
俺圈數(shù)遍歷，注意圈數(shù)的結(jié)束條件 x>2start&&y>2start
注意每次上下左右遍歷執(zhí)行的前提條件

public class test3 {
/*
 * 輸入一個矩陣，按照從外向里以順時針的順序依次打印出每一個數(shù)字，例如，
 * 如果輸入如下矩陣： 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.
 */
    
    void printMartrixMethod(int [][]matrix){
        if(matrix==null||matrix.length==0||matrix[0].length==0)
            return;
        int start=0;
        while((matrix[0].length>start*2)&&(matrix.length>start*2)){
            printMatrix(matrix,start);
            ++start;
        }
    }
    
    public void printMatrix(int [][] matrix,int start) {
        int endx=matrix[0].length-1-start;//中止列號
        int endy=matrix.length-1-start;//中止行號
        for(int i=start;i<=endx;i++){
            int number=matrix[start][i];
            System.out.print(number+" ");
        }
        if(start<endy){//執(zhí)行第二步的前提條件 中止行號大于起始行號start
            for(int i=start+1;i<=endy;i++){
                int number=matrix[i][endx];
                System.out.print(number+" ");
            }
        }
        if(start<endx&start<endy){//執(zhí)行第三部前提 中止行號大于起始行號 中止列號大于起始列號
            for(int i=endx-1;i>=start;i--){
                int number=matrix[endy][i];
                System.out.print(number+" ");
            }
        }
        if(start<endx&&start<endy-1){ //執(zhí)行第四步 至少三行兩列 要求中止行號比起始至少大2
            for(int i=endy-1;i>=start+1;i--){
                int number=matrix[i][start];
                System.out.print(number+" ");
            }
        }
    }
    
    public static void main(String[] args) {
        int a[][]={{1,2,3,4},{5,6,7,8},{9,10,11,12},{13,14,15,16}};
        new test3().printMartrixMethod(a);
    }
}