剑指offer 树的子结构

Posted on |

树的子结构

题目

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

方法

字符表示的方法尚未完成，因为本题目有一个限制条件

方法1：比较结点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# -*- 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
        if pRoot1 is None or pRoot2 is None:
            return False
        return self.judge(pRoot1,pRoot2) or self.judge(pRoot1.left,pRoot2) or self.judge(pRoot1.right,pRoot2)

    def judge(self,s,t):
        # 如果Tree2为空，则说明第二棵树遍历完了，即匹配成功
        if not t:
            return True
        # 如果tree1为空&&tree2不为空说明不匹配
        # 如果tree1为空，tree2为空，说明匹配
        if not s:
            return False
        return s.val==t.val and self.judge(s.left,t.left) and self.judge(s.right,t.right)