剑指offer第二版（Python3）--面试题26：树的子结构

第3章 高质量的代码

  面试题21：调整数组顺序使奇数位于偶数前面

  面试题22：链表中倒数第k个结点

  面试题24 ：翻转链表

  面试题25 ：合并两个排序的链表

  面试题26 ：树的子结构

第4章 解决面试题的思路

第5章 优化时间和空间效率

第6章 面试中的各项能力

第7章 两个面试案例

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

解题思路   先要区分子树和子结构的区别，子树的意思是包含了一个节点，就得包含这个节点下的所有节点，一棵大小为n的二叉树有n个子树，就是分别以每个节点为根的子树。子结构的意思是包含了一个节点，可以只取左子树或者右子树，或者都不取。 分两步：

1. 先写一个方法，传入两棵根节点值相同的树，判断tree1是否和tree2结构一样；
2. 再写一个方法来遍历大树A，找到一个和小树B根节点值相等的节点，以该节点和小树根节点的值为参数调用上面的方法即可。

实战   HasSubtreeCore(root1, root2)用于判断root2是否是以root1为根节点的树的子树。while循环用于遍历树A。

# 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
        def HasSubtreeCore(root1, root2):
            if not root2:
                return True
            if not root1 or root1.val != root2.val:
                return False
            
            left = HasSubtreeCore(root1.left, root2.left)
            right = HasSubtreeCore(root1.right, root2.right)
            return left and right
        
        if not pRoot1 or not pRoot2:
            return False
        
        stack = [pRoot1]
        while stack:
            root = stack.pop()
            if HasSubtreeCore(root, pRoot2):
                return True
            if root:
                stack.append(root.left)
                stack.append(root.right)
        return False