[LeetCode] 872. Leaf-Similar Trees_Easy tag: DFS

时间:2021-09-10 08:17:12

Consider all the leaves of a binary tree.  From left to right order, the values of those leaves form a leaf value sequence.

[LeetCode] 872. Leaf-Similar Trees_Easy tag: DFS

For example, in the given tree above, the leaf value sequence is (6, 7, 4, 9, 8).

Two binary trees are considered leaf-similar if their leaf value sequence is the same.

Return true if and only if the two given trees with head nodes root1 and root2 are leaf-similar.

Note:

  • Both of the given trees will have between 1 and 100 nodes.

思路, DFS, 将所有leaves从左到右append进入leaves里面. 最后比较.

T: O(n1 + n2),    S: O(max(n1,n2))

Code

class Solution:
def leafSimilarTree(self, root1, root2):
def dfs(root, leaves):
if not root: return
if not root.left and not root.right:
leaves.append(root.val)
dfs(root.left, leaves)
dfs(root.right, leaves)
return dfs(root1, []) == dfs(root2, [])