Check if B is Subtree of A

1. Link

树的子结构_牛客题霸_牛客网www.nowcoder.com

2. 题目描述

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

输入

复制

{8,8,#,9,#,2,#,5},{8,9,#,2}

返回值

复制

true

3. 思路

1. 定义一个对比tree A有没有包含tree B的函数

   1. 输入： tree A的某个node， treeB的root node

   2. 如果treeA的树搜索完但B的没有搜索完，就是False

   3. 如果treeB搜索完，就return True （treeB 是treeA的一部分）

   4. 否则对比当前treeA的node 和B的node的value，不一致就return False

2. 在HasSubtree 里面先对比tree A当前的node和tree B的root node，如果一致，就对比以tree A当前的node为root node的subtree和tree B

3. 如果不一致，就对比tree A当前的node的left，right分支有没有包含tree B。

4. Time: O(m) for matching subtree A and tree B, m= number of node in B, O(n) for iterating every node in A. In total: O(m*n)

5. Space: O(logn) for recursion

4. Coding

# -*- 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
        res = False
        if pRoot1 and pRoot2:
            if pRoot1.val == pRoot2.val:
                # start from current node1 and root of B to check 
                res = self.sametree(pRoot1, pRoot2)
            if not res:
                # if doesn't match, start from left subtree, or right
                # subtree to match subtree of A and tree B
                res = self.HasSubtree(pRoot1.left, pRoot2) or self.HasSubtree(pRoot1.right, pRoot2)
        return res
    def sametree(self, node1, node2):
        if (node2 and not node1):
            # if node2 still exist, but node1 doesn't exist
            # then node2 is not subtree of node1
            return False
        if not node2:
            #if node2, B, already checked entirely, but node1 A still
            # exist, then B is subtree, part of A
            return True
        if node1.val != node2.val:
            return False
        f1= self.sametree(node1.left, node2.left) and self.sametree(node1.right, node2.right)
        return f1