Wednesday, May 18, 2022

Easy_Question22 : Leaf-Similar Trees

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.


  • The number of nodes in each tree will be in the range [1, 200].
  • Both of the given trees will have values in the range [0, 200].
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> leafValues) { if (node != null) { if (node.left == null && node.right == null) leafValues.add(node.val); dfs(node.left, leafValues); dfs(node.right, leafValues); } } }

Complexity Analysis

  • Time Complexity: O(T_1 + T_2), where T_1, T_2 are the lengths of the given trees.

  • Space Complexity: O(T_1 + T_2), the space used in storing the leaf values.

You may also like

Kubernetes Microservices
Python AI/ML
Spring Framework Spring Boot
Core Java Java Coding Question
Maven AWS