動機

複習dfs與bfs

Problem

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.

 

Example 1:

Input: p = [1,2,3], q = [1,2,3]Output: true

Example 2:

Input: p = [1,2], q = [1,null,2]Output: false

Example 3:

Input: p = [1,2,1], q = [1,1,2]Output: false

 

Constraints:

  • The number of nodes in both trees is in the range [0, 100].
  • -104 <= Node.val <= 104

Sol

def bfs(root):
    q = deque()
    q.append(root)
    ret = []
    while q:
        r = q.popleft()
        if r:
            q.append(r.left)
            q.append(r.right)
            ret.append(r.val)
        else:
            ret.append(None)
    return ret
def dfs(r, ret):
    if r:
        ret.append(r.val)
        return dfs(r.right,dfs(r.left,ret))
    else:
        ret.append(None)
        return ret
class Solution:
    def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
        return dfs(p,[]) == dfs(q,[])

Sol2

直接在tree上遞迴

class Solution:
    def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
        if p is None and q is None:
            return True
        elif p is None or q is None:
            return False
        else:
            return p.val == q.val and self.isSameTree(p.left,q.left) and self.isSameTree(p.right,q.right)