树的子结构.md

树的子结构

知识点：树

题目描述

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

解题思路

本来的思路是采用任一一种遍历方式对两棵树同时进行遍历，然后看是否是"子串"关系，但是好像这个思路并行不通。 正确思路应该是（直接看代码更清晰）： 算法1： 先判断当前两棵树的根节点是否相同，如果相同则直接应用算法2判断pRoot2是否是pRoot1的子树，否则判断pRoot2是否是pRoot1.left的子树，如果是使用算法2，如果不是再判断pRoot2是否是pRoot1.right的子树，如果是使用算法2，如果还不是那就返回False，如果三种情况有一种满足则调用算法2并传入对应的参数。

算法2（两个根节点相同的树，如何判断一个是否是另一个的子树）： 首先判断Node2是否已经为None，如果是则说明Node2已经遍历完了，返回True 如果Node2不为None则判断Node1是否为None，如果是说明Node2还没为None而Node1却为None了所以返回False 如果Node1和Node2均不为None，递归调用算法2分别判断Node1和Node2的左右子树是否满足子树关系。

代码

    def HasSubtree(self, pRoot1, pRoot2):
        # write code here
        if pRoot1 == None or pRoot2 == None:
            return False
        flag = False
        if pRoot1.val == pRoot2.val:
            flag = self.doseNode1HasNode2(pRoot1, pRoot2)

        if not flag:
            flag = self.HasSubtree(pRoot1.left, pRoot2)

        if not flag:
            flag = self.HasSubtree(pRoot1.right, pRoot2)

        return flag

    def doseNode1HasNode2(self, Node1, Node2):
        if Node2 == None:
            return True
        if Node1 == None:
            return False
        if Node1.val != Node2.val:
            return False

        return self.doseNode1HasNode2(Node1.left, Node2.left) and self.doseNode1HasNode2(Node1.right, Node2.right)

全部代码