剑指17-树的子结构

题目描述

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

---

非递归版本

• 首先遍历A，对其每个节点node用check函数判断其能否对应B的根节点rB，并且B是A的子结构。
• check函数，遍历B，并以B为标准从rB和node核对，B有的结构A也要有，对应节点的值也要相等。
• 一旦核对不上，返回False。
• 直到B遍历结束，返回True。
• 至于遍历顺序是先根、后根、中根（递归，或者用栈），或者层次遍历（用到了队列），都无所谓。

class Solution:
    def HasSubtree(self, pRoot1, pRoot2):
        def check(node, pRoot2):
            # 检查pRoot1的node节点作为起点的树，
            # 是否包含了pRoot2,并且node节点对应pRoot2节点
            # 注意node和pRoot2地位不对等，以pRoot2为准
            q1, q2 = [node], [pRoot2]
            while len(q2) > 0:
                if len(q1) <= 0:
                    return False
                node1, node2 = q1.pop(0), q2.pop(0)
                if node1.val != node2.val:
                    return False
                if node2.left:
                    if not node1.left:
                        return False
                    q1.append(node1.left)
                    q2.append(node2.left)
                if node2.right:
                    if not node1.right:
                        return False
                    q1.append(node1.right)
                    q2.append(node2.right)
            return True
                
        if pRoot2 is None or pRoot1 is None:
            return False
        q = [pRoot1]
        while len(q) > 0:
            node = q.pop(0)
            if node.left:
                q.append(node.left)
            if node.right:
                q.append(node.right)
            if check(node, pRoot2):
                return True
        return False

---

递归版本

• 巧用逻辑短路规则

def HasSubtree(p1, p2):
    def check(r1,r2):
        if r2 is None:
            return True
        elif r1 is None:
            return False
        return r1.val == r2.val and check(r1.left, r2.left) and check(r1.right, r2.right)
    if p1 is None or p2 is None:
        return False
    else:
        return check(p1, p2) or HasSubtree(p1.left, p2) or HasSubtree(p1.right, p2)