另一个树的子树.md

572.另一个树的子树

题目

给定两个非空二叉树 s 和 t，检验 s 中是否包含和 t 具有相同结构和节点值的子树。s 的一个子树包括 s 的一个节点和这个节点的所有子孙。s 也可以看做它自身的一棵子树。

给定的树 s:
      3
     / \
    4   5
   / \
  1   2
给定的树 t：
  4
 / \
1   2
返回 true，因为 t 与 s 的一个子树拥有相同的结构和节点值。

分析

迭代，遍历s树，如果子树的根节点与t树的根节点相等，再去判断两个数是否相等，相同的树

from queue import Queue
def isSubtree(s, t):
    def isSame(p, q):
        if p is None and q is None:
            return True
        if not p or not q:
            return False
        if p.val != q.val:
            return False
        else:
            return isSame(p.left, q.left) and isSame(p.right, q.right)

    Q = Queue()
    Q.put(s)
    while Q.qsize():
        node = Q.get()
        if node.val == t.val:
            if isSame(node, t):
                return True
            else:
                if node.left:
                    Q.put(node.left)
                if node.right:
                    Q.put(node.right)
        else:
            if node.left:
                Q.put(node.left)
            if node.right:
                Q.put(node.right)
    return False