import java.util.*;
/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;
    public TreeNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {
    public boolean HasSubtree(TreeNode root1,TreeNode root2) {
        if(root1==null || root2==null) return false;//题目要求，空树不是任何树的子结构
        return IsChildTree(root1,root2)||HasSubtree(root1.left,root2)||
            HasSubtree(root1.right,root2);
      }  
       //当两颗树根节点相同时 判断root1 是否和root2结构一样
       boolean IsChildTree(TreeNode root1,TreeNode root2){
        if(root2==null) return true;
        if(root1==null) return false;
        if(root1.val!=root2.val && root2.val!=root1.val) return false;
    return IsChildTree(root1.left,root2.left)&&IsChildTree(root1.right,root2.right);
    }
}   

import java.util.*;
/*
public class ListNode {
    int val;
    ListNode next = null;
    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode Merge(ListNode list1,ListNode list2) {
        ListNode head=new ListNode(-1);//新建一个虚拟头结点 用来合并链表
        head.next=null;
        ListNode root=head;
        while(list1!=null&&list2!=null){ //如果list1的结点值小于list2的结点值 则将
            //lsit1指向的结点值接到head的next指针后面 然后指向下一个节点
            if(list1.val<list2.val){ //否则让 list2指向下一个节点
                head.next=list1;
                head=list1;
                list1=list1.next;
            }else{
                head.next=list2;
                head=list2;
                list2=list2.next;
            }
        }
        //把未结束的链表连接到合并后的链表尾部
        if(list1!=null) head.next=list1; //最后将剩下的部分连接到root后面
        if(list2!=null) head.next=list2;
        return root.next;
    }
}