572. Subtree of Another Tree

问题描述

Given two non-empty binary trees s and t, check whether tree t has exactly the same structure and node values with a subtree of s. A subtree of s is a tree consists of a node in s and all of this node's descendants. The tree s could also be considered as a subtree of itself.

思路

• 大的method里，调用isSame判断s跟t是不是一样；如果不是的话就去recurs.left和s.right.

1. 在isSame的方法中，如果两个都是空，说明刚好到头，是一致的，返回True；如果是有一个为空，说明不一致，返回False
2. 判断了结构之后，开始看数值，不一样则返回False
3. 否则，recur两棵树的左右两边

class Solution(object):
    def isSame(self, s, t):
        if s == None and t == None:
            return True
        if s == None or t == None:
            return False
        if s.val != t.val:
            return False
        return self.isSame(s.left, t.left) and self.isSame(s.right, t.right)
    
    def isSubtree(self, s, t):
        """
        :type s: TreeNode
        :type t: TreeNode
        :rtype: bool
        """
        if s == None:
            return False
        if self.isSame(s,t):
            return True
        return self.isSubtree(s.left, t) or self.isSubtree(s.right, t)