問題描述

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里，調(diào)用isSame判斷s跟t是不是一樣；如果不是的話就去recurs.left和s.right.

1. 在isSame的方法中，如果兩個(gè)都是空，說明剛好到頭，是一致的，返回True；如果是有一個(gè)為空，說明不一致，返回False
2. 判斷了結(jié)構(gòu)之后，開始看數(shù)值，不一樣則返回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)