[LeetCode] #100. Same Tree

題目

Given the roots of two binary trees p and q, write a function to check if they are the same or not.
Two binary trees are considered the same if they are structurally identical, and the nodes have the same value.

直覺解

構想一：

參考 94. Binary Tree Inorder Traversal，用 Inorder 的方式，遍歷整棵樹，並檢查每個節點的值是否相同

python 3 實作：

def isSameTree(self, p: TreeNode, q: TreeNode) -> bool: 

    stack_p = [] 

    stack_q = [] 

    while stack_p or stack_q or p or q: 

        if len(stack_p) != len(stack_q): 

            return False 

        if (not p and q) or (p and not q): 

            return False 

             

        if p or q: 

            stack_p.append(p) 

            stack_q.append(q) 

            p = p.left 

            q = q.left 

        else: 

            p = stack_p.pop(len(stack_p) - 1) 

            q = stack_q.pop(len(stack_q) - 1) 

            if p.val != q.val: 

                return False 

            p = p.right 

            q = q.right 

    return True

效能：

Runtime: 32 ms, faster than 59.16% of Python3 online submissions for Same Tree.
Memory Usage: 14.4 MB, less than 28.71% of Python3 online submissions for Same Tree.

構想二：

依照 中間-左邊-右邊 的順序用遞回的方式比對

python 3 實作：

def isSameTree(self, p: TreeNode, q: TreeNode) -> bool: 

    if (not p and q) or (p and not q): 

        return False 

    if p and q: 

        if p.val != q.val: 

            return False 

        return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right) 

    return True

犯過的錯誤

• 因為是 class instance，所以要用 self.isSameTree 呼叫函式，沒加 self. 的話會變成 is not defined

效能：

Runtime: 28 ms, faster than 83.88% of Python3 online submissions for Same Tree.
Memory Usage: 14.3 MB, less than 28.92% of Python3 online submissions for Same Tree.

參考別人的遞迴解後，python 3 易讀性優化：

def isSameTree(self, p: TreeNode, q: TreeNode) -> bool: 

    if not p and not q: 

        return True 

         

    if not p or not q: 

        return False 

         

    if p.val != q.val: 

        return False 

         

    return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)

效能：

第一次

Runtime: 48 ms, faster than 8.39% of Python3 online submissions for Same Tree.
Memory Usage: 14.3 MB, less than 28.92% of Python3 online submissions for Same Tree.

第二次

Runtime: 52 ms, faster than 5.81% of Python3 online submissions for Same Tree.
Memory Usage: 14.4 MB, less than 28.92% of Python3 online submissions for Same Tree.

第三次

Runtime: 60 ms, faster than 5.81% of Python3 online submissions for Same Tree.
Memory Usage: 14 MB, less than 95.68% of Python3 online submissions for Same Tree.

第四次

Runtime: 28 ms, faster than 83.88% of Python3 online submissions for Same Tree.
Memory Usage: 14.2 MB, less than 84.85% of Python3 online submissions for Same Tree.