Skip to content

872. Leaf-Similar Trees 👍

  • Time: $O(T_1 + T_2)$
  • Space: $O(T_1 + T_2)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
 public:
  bool leafSimilar(TreeNode* root1, TreeNode* root2) {
    vector<int> leaves1;
    vector<int> leaves2;
    dfs(root1, leaves1);
    dfs(root2, leaves2);
    return leaves1 == leaves2;
  }

  void dfs(TreeNode* root, vector<int>& leaves) {
    if (root == nullptr)
      return;
    if (root->left == nullptr && root->right == nullptr) {
      leaves.push_back(root->val);
      return;
    }

    dfs(root->left, leaves);
    dfs(root->right, leaves);
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
  public boolean leafSimilar(TreeNode root1, TreeNode root2) {
    List<Integer> leaves1 = new ArrayList<>();
    List<Integer> leaves2 = new ArrayList<>();
    dfs(root1, leaves1);
    dfs(root2, leaves2);
    return leaves1.equals(leaves2);
  }

  public void dfs(TreeNode node, List<Integer> leaves) {
    if (node == null)
      return;
    if (node.left == null && node.right == null) {
      leaves.add(node.val);
      return;
    }

    dfs(node.left, leaves);
    dfs(node.right, leaves);
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
  def leafSimilar(self, root1: TreeNode | None, root2: TreeNode | None) -> bool:
    def dfs(root: TreeNode | None) -> None:
      if not root:
        return
      if not root.left and not root.right:
        yield root.val
        return

      yield from dfs(root.left)
      yield from dfs(root.right)

    return list(dfs(root1)) == list(dfs(root2))