【LeetCode】剑指 Offer（9）

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
    }
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        //建一个哨兵位的头结点
        ListNode* head = new ListNode(0);
        //新链表的头指针
        ListNode* cur = head;
        //归并
        while(l1 && l2)
        {
            if(l1->val < l2->val)
            {
                cur->next = l1;
                l1 = l1->next;
            }
            else
            {
                cur->next = l2;
                l2 = l2->next;
            }
            cur = cur->next;
        }
        //如果有一个链表遍历完了，那就
        //直接用新链表的尾将剩下的那个链表接上
        cur->next = (l1 == nullptr ? l2 : l1);
        //返回新链表的头
        return head->next;
    }
};

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isSubStructure(TreeNode* A, TreeNode* B) {
    }
};

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool is_SubStructure(TreeNode* A, TreeNode* B)
    {
        //如果递归到空节点，证明B是A的子结构
        if(B == nullptr)
        {
            return true;
        }
        //如果A走到空节点，或者不相等，返回false
        if(A == nullptr || A->val != B->val)
        {
            return false;
        }
        //比较左孩子和右孩子
        return is_SubStructure(A->left, B->left) && is_SubStructure(A->right, B->right);
    }
    bool isSubStructure(TreeNode* A, TreeNode* B) {
        //判断树是否为空
        if(A == nullptr || B == nullptr)
        {
            return false;
        }
        //递归比较节点                  //遍历二叉树
        return is_SubStructure(A, B) || isSubStructure(A->left, B) || isSubStructure(A->right, B);
    }
};