9.19~9.20刷题总结

使二叉树变为其镜像
类似先序遍历的方法

    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);
    }

判断二叉树是否对称
左节点的右子树和右节点的左子树相同 使用递归

    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);
    }

实现有Min函数的栈

    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;
        }

求字符串全排列结果 按字典顺序返回
划分为子问题 第一个数和后面每个数交换 第二个数和后面每个数交换 ...

    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;
        }
    }

克隆复杂链表 该链表两个指针 一个指向下一个 一个随机指向
思路：
第一步：根据原始链表每个节点N创建对应的N'，把N'链接到N后面
第二步：根据原始链表每个节点N的random指针，设置新节点的random指针，为原指针的下一位
第三步：将第二步得到的链表拆分，奇数位置是原始链表，偶数位置是复制出来的链表 实现过程的一些细节要注意

//根据原始链表每个节点N创建对应的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;
        }
    }
//根据原始链表每个节点N的random指针，设置新节点的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）时间删除链表非尾节点的节点
将下一个节点的值复制给该节点，删除下一个节点，调整链接。

    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;
        }
    }

顺时针打印矩阵
俺圈数遍历，注意圈数的结束条件 x>2start&&y>2start
注意每次上下左右遍历执行的前提条件

public class test3 {
/*
 * 输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，
 * 如果输入如下矩阵： 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.
 */
    
    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){//执行第二步的前提条件 中止行号大于起始行号start
            for(int i=start+1;i<=endy;i++){
                int number=matrix[i][endx];
                System.out.print(number+" ");
            }
        }
        if(start<endx&start<endy){//执行第三部前提 中止行号大于起始行号 中止列号大于起始列号
            for(int i=endx-1;i>=start;i--){
                int number=matrix[endy][i];
                System.out.print(number+" ");
            }
        }
        if(start<endx&&start<endy-1){ //执行第四步 至少三行两列 要求中止行号比起始至少大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);
    }
}