劍指offer：樹的子結(jié)構(gòu)

題目描述
輸入兩棵二叉樹A，B，判斷B是不是A的子結(jié)構(gòu)。（ps：我們約定空樹不是任意一個(gè)樹的子結(jié)構(gòu)）

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:
    def HasSubtree(self, pRoot1, pRoot2):
        def helper(root1, root2):
            # 如果root2已經(jīng)遍歷完了，說明root2的每一個(gè)節(jié)點(diǎn)都能在pRoot1找到對應(yīng)的節(jié)點(diǎn)
            if not root2:
                return True
            # 如果pRoot1遍歷完而pRoot2還沒遍歷完，說明這root1不是對應(yīng)的子樹根節(jié)點(diǎn)
            if not root1:
                return False
            # 如果遍歷過程中存在值不相等的節(jié)點(diǎn)，說明不是要找的子樹
            if root1.val != root2.val:
                return False
            # 如果當(dāng)前節(jié)點(diǎn)的值相同，那么繼續(xù)遍歷剩下的節(jié)點(diǎn)
            return (helper(root1.left, root2.left)
                    and helper(root1.right, root2.right))

        # 由于題目規(guī)定，空樹不是子結(jié)構(gòu)，所以特殊處理這種情況
        if not pRoot2 or not pRoot1:
            return False

        res = False
        # 首先找到pRoot1中與pRoot2的根節(jié)點(diǎn)的值相同的節(jié)點(diǎn)root1，
        # 然后按照與pRoot2相同的順序去遍歷找到的root1，如果以root1為根節(jié)點(diǎn)的子樹和pRoot2一樣
        # 那么說明在pRoot1中找到了跟pRoot2一樣的子樹。
        if pRoot1.val == pRoot2.val:
            res = helper(pRoot1, pRoot2)
        if not res:
            # 遞歸遍歷pRoot1，直到找到一個(gè)子樹或者遍歷完整棵樹
            res = self.HasSubtree(pRoot1.left, pRoot2) \
                  or self.HasSubtree(pRoot1.right, pRoot2)
        return res