4/4-剑指offer

1.合并两个排序的链表
思路：首先对比两个链表的第一个节点，将较小的当作新链表的第一个节点，然后把下一个节点与之前较大的节点相比较，此处可用递归来进行。（注意鲁棒性，当链表为nullptr时应该怎么做。）

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
            val(x), next(NULL) {
    }
};*/
class Solution {
public:
    ListNode* Merge(ListNode* pHead1, ListNode* pHead2)
    {
        if(pHead1==nullptr)
            return pHead2;
        if(pHead2==nullptr)
            return pHead1;
        ListNode* newHead=nullptr;
        if(pHead1->val<pHead2->val)
        {
            newHead=pHead1;
            newHead->next=Merge(pHead1->next,pHead2);
        }
        else if(pHead1->val>=pHead2->val)
        {
            newHead=pHead2;
            newHead->next=Merge(pHead1,pHead2->next);
        }
        return newHead;
    }
};

2.树的子结构
思路：首先两树的根节点先进行比较，如果相等，则判断这两个根节点的左右子树是否相等，这里也利用递归进行。需要设计两个函数：一个遍历二叉树，一个遍历根节点相同时左右子树是否对应相等。（注意代码的鲁棒性，在每一次需要访问地址的时候都问自己这个地点有没有可能是nullptr）

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};*/
class Solution {
public:
    bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2)
    {
        bool result=false;
        if(pRoot1!=NULL&&pRoot2!=NULL)
        {
            if(pRoot1->val==pRoot2->val)
                result=dfs(pRoot1,pRoot2);//若根节点相同，进dfs继续比
            if(!result)
                result=HasSubtree(pRoot1->left,pRoot2);//不等的话，拿左子树头结点比
            if(!result)
                result=HasSubtree(pRoot1->right,pRoot2);//再不等的话，拿右子树头结点比
        }
        return result;         
    }
    bool dfs(TreeNode* pRoot1, TreeNode* pRoot2)
    {
        if(pRoot2==NULL) return true;//B树遍历完都对应的上，返回真
        if(pRoot1==NULL) return false;//A树先遍历完了，B还没遍历完，返回假
        if(pRoot1->val!=pRoot2->val)
            return false;//有一会不相等就返回假
        else//相等则继续比
            return dfs(pRoot1->left, pRoot2->left)&&dfs(pRoot1->right, pRoot2->right);    
    }
};