Leetcode # 872. Leaf-Similar Trees

https://leetcode.com/problems/leaf-similar-trees/

Solution

Time Complexity: O(len(tree1 + tree2))
Space Complexity: O(len(tree1 + tree2))
(The input and output generally do not count towards the space complexity.)

Python 竟然可以直接用 == 比較 list 相同與否…

class Solution:
  def leafSimilar(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:
    leaves = [[], []]

    for i, root in enumerate([root1, root2]):
      stack = [root]
      while stack:
        cur = stack.pop()
        if not cur.left and not cur.right:
          leaves[i].append(cur.val)
        else:
          if cur.left:
            stack.append(cur.left)
          if cur.right:
            stack.append(cur.right)
    return leaves[0] == leaves[1]

Last Updated on 2023/08/16 by A1go