“This is the 19th day of my participation in the Gwen Challenge in November. See details: The Last Gwen Challenge in 2021”.

LeetCode 200 simple questions

Topic describes

Given the root nodes p and q of two binary trees, write a function to check whether the two trees are the same.

Two trees are considered identical 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

prompt

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

Their thinking

In this case, depth-first search is suitable, while breadth-first search is more complicated. First, if both binary trees are empty, the two binary trees are the same and return True. If only one of the two binary trees is empty or the val of the two binary trees is different, then the two binary trees must be different, which does not meet the meaning of the question, return False, if the above conditions are not met, then determine whether the left and right subtrees of the two binary trees are the same. This is typically a recursive process, so a depth-first search can be used to recursively determine whether two binary trees are the same.

# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution(object) :
    def isSameTree(self, p, q) :
        """ :type p: TreeNode :type q: TreeNode :rtype: bool """
        # return True if both p and q are null
        if not p and not q:
            return True
        Return False if one and only one of # p and q is empty, or if p and q differ in 'val'
        elif (not p or not q) or(p.val ! = q.val):return False
        Determine whether the left and right subtrees of p and Q are the same
        else:
            return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)
Copy the code
  • Time complexity: O(min(m,n))
  • Space complexity: O(min(m,n))

Clocked in today, the current progress is 9/200.

This is what I want to share today. Search Python New Horizons on wechat, bringing you more useful knowledge every day. More organized nearly a thousand sets of resume templates, hundreds of e-books waiting for you to get oh! In addition, there are Python small white communication group, if you are interested in the way to contact me!