面试题26: 树的子结构

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

解题思路：
这道题考的是树的遍历，利用递归来实现，在节点不为空的情况下首先判断根节点是否相同，相同的话进入结构是否相同的函数进行递归得到bool值hasSub，不同的话判断左节点与b的根节点是否相同，如果还是不同的话判断右节点与根节点是否相同，然后返回HasSub值，具体如下：

26 树的子结构.png

代码实现：

# -*- 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
        HasSub = False
        if pRoot1 and pRoot2:
            if self.equal(pRoot1.val,pRoot2.val):        #比较值的大小
                HasSub = self.IsSub(pRoot1,pRoot2)
            if not HasSub:                               #如果没有子树，再进行左节点与b的根节点判断
                HasSub = self.HasSubtree(pRoot1.left,pRoot2)
            if not HasSub:                                #如果左节点与根节点有子树结构 不再继续
                HasSub = self.HasSubtree(pRoot1.right,pRoot2)
        return HasSub

    def IsSub(self,pRoot1,pRoot2):     #判断是否有子树的相同结构
        if pRoot2 == None:
            return True
        if pRoot1== None:
            return False
        if self.equal(pRoot1.val, pRoot2.val):
            return self.IsSub(pRoot1.left,pRoot2.left) and self.IsSub(pRoot1.right,pRoot2.right)
        else:
            return False
    def equal(self,num1,num2):
        if abs(num1-num2)<1e-7:
            return True
        else:
            return False

*递归的整个调用过程图示

手写调用过程

提交结果：

牛客网提交结果

·