872. Leaf-Similar Trees LeetCode Solution

In this guide, you will get 872. Leaf-Similar Trees LeetCode Solution with the best time and space complexity. The solution to Leaf-Similar Trees problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Leaf-Similar Trees solution in C++
Leaf-Similar Trees solution in Java
Leaf-Similar Trees solution in Python
Additional Resources

872. Leaf-Similar Trees LeetCode Solution image

Problem Statement of Leaf-Similar Trees

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

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.

Example 1:

Input: root1 = [3,5,1,6,2,9,8,null,null,7,4], root2 = [3,5,1,6,7,4,2,null,null,null,null,null,null,9,8]
Output: true

Example 2:

Input: root1 = [1,2,3], root2 = [1,3,2]
Output: false

Constraints:

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].

Complexity Analysis

Time Complexity: O(T_1 + T_2)
Space Complexity: O(T_1 + T_2)

872. Leaf-Similar Trees LeetCode Solution in C++

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);
  }
};
/* code provided by PROGIEZ */

872. Leaf-Similar Trees LeetCode Solution in Java

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);
  }
}
// code provided by PROGIEZ

872. Leaf-Similar Trees LeetCode Solution in Python

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))
 # code by PROGIEZ