Java日记2018-06-01

25. 合并两个排序的链表
    使用递归合并，很有意义，值得认真再细看一下

//有序链表的合并
    public static ListNode merge(ListNode lst1,ListNode lst2) {
        if(lst1==null) return lst2;
        if(lst2==null) return lst1;
        if(lst1.val<lst2.val) {
            lst1.next=merge(lst1.next,lst2);
            return lst1;
        } else {
            lst2.next=merge(lst1,lst2.next);
            return lst2;
        }
        
    }

26. 树的子结构

题解答案是错的，上次居然没看出来，按照题解来的话，如果root1=root2那么就会溢出保持

public static boolean HasSubtree(TreeNode root1,TreeNode root2) {
        if(root1==null || root2==null) return false;
        //下面其实包含三部分，root1==root2那么要同时满足root1.left,root2.left与root1.right,root2.right。root1!=root2那么从root1的左树开始找，或从root1的右树开始找
        return (hassubtreecore(root1.left,root2.left)&&hassubtreecore(root1.right,root2.right)) || hassubtreecore(root1.left,root2) || hassubtreecore(root1.right,root2);
    }
    public static boolean hassubtreecore(TreeNode root1,TreeNode root2) {
        if(root2==null) return true;
        if(root1 ==null) return false;
        if(root1.val!= root2.val) return false;
        
        return hassubtreecore(root1.left,root2.left)||hassubtreecore(root1.right,root2.left);
    }

27. 二叉树的镜像

树的算法里面很多递归的使用，多练练

//二叉树的镜像
    public static void mirror(TreeNode root) {
        if(root==null) return;
        swap(root);
        mirror(root.left);
        mirror(root.right);
        
    }
    public static void swap(TreeNode root){
        TreeNode t = root.left;
        root.left = root.right;
        root.right = t;
    }