Leetcode 872. Leaf-Similar Trees

Problem Explanation

In this problem, we are given two binary trees and we are asked to check if these trees are "leaf similar".

A binary tree is a tree data structure in which each node has at most two children, referred to as the left child and the right child. Leaves of a binary tree are the nodes that have no children, i.e. their left and right child are both null.

Two binary trees are considered "leaf similar" if their sequences of leaf nodes (from left to right) are the same. It means that when you traverse the leaves of both trees from left to right, they yield the same integer values

To summarize the problem, we need to traverse the two given trees, record the sequence of leaf nodes in each_tree, then compare the two sequences. If they are the same, we return true; else we return false.

For example, given two trees:

1  Tree 1                Tree 2
2    1                      2
3   / \                    / \
4  2   3                  2   3
5 / \  / \                / \  / \
64  5 6  7               4  5 6  7

In both trees, the leaf value sequence is (4,5,6,7), thus they are leaf similar and we should return true.

Solution Approach

We can solve this problem using Depth-First Search (DFS) algorithm. We simply start at the root of each tree and explore as far as possible along each branch before backtracking. As we do DFS, we check if the current node is a leaf node (it's a leaf if it has no children; i.e., the left and right child are both null). If it is, we add its value to a list.

At the end, we would have two lists each containing the leaf sequence of one tree. If these lists are equal, then we can say the trees are leaf-similar; else they are not.

Solution in Python

1
2python
3class Solution:
4    def leafSimilar(self, root1, root2):
5        def dfs(node):
6            if node != None:
7                if node.left == node.right:
8                    yield node.val
9                yield from dfs(node.left)
10                yield from dfs(node.right)
11        return list(dfs(root1)) == list(dfs(root2))

Solution in Java

1
2java
3class Solution {
4    public boolean leafSimilar(TreeNode root1, TreeNode root2) {
5        ArrayList<Integer> leaves1 = new ArrayList();
6        ArrayList<Integer> leaves2 = new ArrayList();
7        dfs(root1, leaves1);
8        dfs(root2, leaves2);
9        return leaves1.equals(leaves2);
10    }
11
12    public void dfs(TreeNode node, List<Integer> leafValues) {
13        if (node != null) {
14            if (node.left == null && node.right == null)
15                leafValues.add(node.val);
16            dfs(node.left, leafValues);
17            dfs(node.right, leafValues);
18        }
19    }
20}

Solution in JavaScript

1
2javascript
3var leafSimilar = function(root1, root2) {
4    let dfs = (node, leafValues) => {
5        if (node != null) {
6            if (node.left == null && node.right == null)
7                leafValues.push(node.val);
8            dfs(node.left, leafValues);
9            dfs(node.right, leafValues);
10        }
11    }
12
13    let leafValues1 = [];
14    let leafValues2 = [];
15    
16    dfs(root1, leafValues1);
17    dfs(root2, leafValues2);
18
19    return leafValues1.toString() == leafValues2.toString();
20};

Solution in C++

1
2cpp
3class Solution {
4public:
5    bool leafSimilar(TreeNode* root1, TreeNode* root2) {
6        vector<int> leaves1;
7        vector<int> leaves2;
8        dfs(root1, leaves1);
9        dfs(root2, leaves2);
10        return leaves1 == leaves2;
11    }
12
13    void dfs(TreeNode* node, vector<int>& leafValues) {
14        if (node != nullptr) {
15            if (node->left == nullptr && node->right == nullptr)
16                leafValues.push_back(node->val);
17            dfs(node->left, leafValues);
18            dfs(node->right, leafValues);
19        }
20    }
21};

Solution in C#

1
2csharp
3public class Solution {
4    public bool LeafSimilar(TreeNode root1, TreeNode root2) {
5        List<int> leafValues1 = new List<int>();
6        List<int> leafValues2 = new List<int>();
7        FillLeafValues(root1, leafValues1);
8        FillLeafValues(root2, leafValues2);
9        return leafValues1.SequenceEqual(leafValues2);
10    }
11
12    private void FillLeafValues(TreeNode root, List<int> leafValues) {
13        if (root == null) {
14            return;
15        }
16        if (root.left == null && root.right == null) {
17            leafValues.Add(root.val);
18        }
19        FillLeafValues(root.left, leafValues);
20        FillLeafValues(root.right, leafValues);
21    }
22}

These codes make a depth-first-search on both trees to gather the leaf nodes in an array (or list). If the arrays/lists are equal, it returns true; otherwise false.All the solutions shared above make use of Depth-First Search to traverse the trees and gather leaf nodes. They are comprehensive and well-explained for different programming languages. The time complexity for each solution is O(N), where N is the number of nodes in the given trees. The space complexity is also O(N), as we are storing the leaf nodes in the list or array.

Let's analyze each language solution :

Python: Python's dynamic nature along with generator function 'yield' makes the code concise and easy to understand. It is using a generator to lazily produce the leaf values during the traversal and storing them in a list.

Java: The Java solution is using an ArrayList to store the leaf nodes. The 'equals' method is used to check the equality of two lists, which internally checks the equality of all elements in those lists.

JavaScript: JavaScript solution is using an array to store the leaf nodes. It is using the 'toString' method to convert the arrays into string format and then comparing them.

C++: C++ solution is similar to the Java solution. It uses a vector to store the leaf nodes and compares the vectors using '==' operator.

C#: This solution in C# uses Lists to store leaf values. The 'SequenceEqual' method is used to verify that two sequences are equal by comparing the elements by using the default equality comparer for their type.

In conclusion, the task of finding similar leaf nodes in different trees can be efficiently handled using the Depth-First Search approach. The solutions provided effectively iterate over all nodes of the trees, list down leaf nodes and compare them to ascertain similarity. They are simple, easy to implement, and widely applicable.