题目描述

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

解题思路

(1)判断二叉树A，B是否为空
(2)判断两棵树的根结点是否相等，若相等则继续遍历两棵树，二叉树A遍历完，B树未遍历完，不符合
二叉树A未遍历完，二叉树B遍历完，符合.
(3)若根结点的值不相等，判断A的根结点的左子节点或右子节点与B的根结点是否相等。

  1. # -*- coding:utf-8 -*-
  2. # class TreeNode:
  3. #     def __init__(self, x):
  4. #         self.val = x
  5. #         self.left = None
  6. #         self.right = None
  7. class Solution:
  8.     def HasSubtree(self, pRoot1, pRoot2):
  9.         result = False
  10.         if pRoot1 is None or pRoot2 is None:
  11.             return False
  12.         #根结点值相同，判断B树是否为A树的子结构
  13.         if pRoot1.val == pRoot2.val:
  14.             result = self.isSubTree(pRoot1,pRoot2)
  15.         #如果还没能在A树中找到与B树相匹配的片段
  16.         if result is False:
  17.             result = self.HasSubtree(pRoot1.left, pRoot2)|self.HasSubtree(pRoot1.right,pRoot2)
  18.         return result
  19.     def isSubTree(self,pRoot1,pRoot2):
  20.         #B树遍历完
  21.         if pRoot2 is None:
  22.             return True
  23.         #B树为遍历完，A树遍历完
  24.         if pRoot1 is None:
  25.             return False
  26.         #若值不相等，返回False
  27.         if pRoot1.val != pRoot2.val:
  28.             return False
  29.         #相等则继续判断子节点
  30.         else:
  31.             return self.isSubTree(pRoot1.left,pRoot2.left) and self.isSubTree(pRoot1.right, pRoot2.right)