劍指offer：樹的子結構

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

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已經遍歷完了，說明root2的每一個節點都能在pRoot1找到對應的節點
            if not root2:
                return True
            # 如果pRoot1遍歷完而pRoot2還沒遍歷完，說明這root1不是對應的子樹根節點
            if not root1:
                return False
            # 如果遍歷過程中存在值不相等的節點，說明不是要找的子樹
            if root1.val != root2.val:
                return False
            # 如果當前節點的值相同，那么繼續遍歷剩下的節點
            return (helper(root1.left, root2.left)
                    and helper(root1.right, root2.right))

        # 由于題目規定，空樹不是子結構，所以特殊處理這種情況
        if not pRoot2 or not pRoot1:
            return False

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