剑指offer系列（七）合并两个排序链表，树的子结构

53 阅读 0 评论 35 点赞

我是靠谱客的博主神勇龙猫，最近开发中收集的这篇文章主要介绍剑指offer系列（七）合并两个排序链表，树的子结构，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

合并两个排序链表

题目描述

输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。

解题思路：

递归思想

代码:

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    # 返回合并后列表
    def Merge(self, pHead1, pHead2):
        # write code here
        if pHead1 == None:
            return pHead2
        if pHead2 == None:
            return pHead1
        
        mergepHead = None
        if pHead1.val<=pHead2.val:
            mergepHead = pHead1
            mergepHead.next = self.Merge(pHead1.next, pHead2)
        elif pHead1.val > pHead2.val:
            mergepHead = pHead2
            mergepHead.next = self.Merge(pHead1, pHead2.next)
            
        return mergepHead

法二：非递归

代码:

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    # 返回合并后列表
    def Merge(self, pHead1, pHead2):
        # write code here
        dummy = ListNode(0)
        pHead = dummy
        
        while pHead1 and pHead2:
            if pHead1.val<=pHead2.val:
                dummy.next = pHead1
                pHead1 = pHead1.next
            else:
                dummy.next = pHead2 
                pHead2 = pHead2.next
            dummy = dummy.next
        if pHead1:
            dummy.next = pHead1
        elif pHead2:
            dummy.next = pHead2
        return pHead.next

树的子结构

题目描述

输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）

解题思路：

两个子序列确定一棵树,不能单个序列模式匹配。因为树的结构确定不了。

方法：

根节点是否相同，相同，递归判断左右子树，递归。不相同，pRoot左右子树与pRoot2判断是否相同，递归。

代码:

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def HasSubtree(self, pRoot1, pRoot2):
        # write code here
        result = False #根节点
        if pRoot1 != None and pRoot2 !=None:
            if pRoot1.val == pRoot2.val: 
                result = self.same(pRoot1,pRoot2)
            if not result:
                result = self.HasSubtree(pRoot1.left, pRoot2)
            if not result:
                result = self.HasSubtree(pRoot1.right, pRoot2)
        return result
    
    def same(self, pRoot1, pRoot2):
        if pRoot2 == None:
            return True
        if pRoot1 == None:
            return False
        #不断 判断 下个节点， 递归
        if pRoot1.val != pRoot2.val:
            return False
        return self.same(pRoot1.left, pRoot2.left) and self.same(pRoot1.right, pRoot2.right)