Leaf-Similar Trees

class Solution {
public:
    bool leafSimilar(TreeNode* root1, TreeNode* root2) {
        vector<int> leafSet1;
        vector<int> leafSet2;
        traverse(root1, leafSet1);
        traverse(root2, leafSet2);

        return leafSet1 == leafSet2;
    }

    void traverse(TreeNode* node, vector<int>& leafNodes) {
        if (node == NULL) return;
        if (node->left == NULL && node->right == NULL)
            leafNodes.push_back(node->val);
        traverse(node->left, leafNodes);
        traverse(node->right, leafNodes);
    }
};

This solution aims to determine if two binary trees are leaf-similar, which means that the sequence of leaf values in both trees is identical when traversed from left to right. This is achieved in CPP using a class named Solution with two main functionalities.

The class has two public methods:

• bool leafSimilar(TreeNode* root1, TreeNode* root2): This is the primary function called with the roots of two binary trees. It checks if the trees have the same leaf sequence.
• void traverse(TreeNode* node, vector<int>& leafNodes): A helper method that traverses the binary tree recursively, storing leaf node values in a vector.

Review the steps taken within each method:

1. leafSimilar Method:

2. Initiate two integer vectors, leafSet1 and leafSet2, to hold the values of leaf nodes for both trees.

3. Utilize the traverse method to populate these vectors for each tree.

4. Return the comparison result of both vectors with ==, determining if the sequences are identical.

5. traverse Method:

6. Check if the current node is NULL; if so, terminate the recursive call.

7. Determine if the current node is a leaf (no left or right children) and, if true, append its value to the leafNodes vector.

8. Recursively call itself for the left and then the right child of the current node.

This method efficiently gathers and compares leaf sequences using vectors, resulting in a clean and straightforward solution. The use of recursion in the traverse method allows the solution to handle trees of different structures and sizes effectively.

class Solution {
    public boolean leafSimilar(TreeNode node1, TreeNode node2) {
        List<Integer> leafSeq1 = new ArrayList<>();
        List<Integer> leafSeq2 = new ArrayList<>();
        traverse(node1, leafSeq1);
        traverse(node2, leafSeq2);
        return leafSeq1.equals(leafSeq2);
    }

    public void traverse(TreeNode current, List<Integer> leafList) {
        if (current != null) {
            if (current.left == null && current.right == null)
                leafList.add(current.val);
            traverse(current.left, leafList);
            traverse(current.right, leafList);
        }
    }
}

The provided solution aims to determine if two binary trees are leaf-similar, meaning they have the same sequence of leaf values from left to right. The code is implemented in Java and consists of a class named Solution with two primary methods:

• leafSimilar(TreeNode node1, TreeNode node2): This method initiates the process by creating two lists, leafSeq1 and leafSeq2, to store the leaf values of two trees respectively. It then calls the traverse method on each tree to populate these lists. Finally, it compares both lists using the equals method to check for similarity in their sequences.

• traverse(TreeNode current, List<Integer> leafList): This is a recursive helper method that takes a node and a list as input. The method traverses the tree depth-first. If a leaf node is encountered (a node with no children), its value is added to the list. The method proceeds to recursively visit the left and then the right child of the current node.

This approach ensures that all leaf nodes are collected in their respective lists and then a straightforward comparison of these lists determines the leaf-similarity of the trees. Use this solution to effectively compare the leaf sequences of any two binary trees for similarity.

var treesLeafSimilar = function(rootA, rootB) {
    explore = function(node, leafVals) {
        if (node) {
            if (!node.left && !node.right) {
                leafVals.push(node.val);
            }
            explore(node.left, leafVals);
            explore(node.right, leafVals);
        }
    }
    let leafList1 = [];
    let leafList2 = [];
    explore(rootA, leafList1);
    explore(rootB, leafList2);

    return (leafList1.length === leafList2.length &&
            leafList1.every((value, index) => value === leafList2[index]));
};

The provided JavaScript function treesLeafSimilar determines if two binary trees are leaf-similar. Leaf-similar trees have the same sequence of leaf node values when trees are traversed in a pre-order depth-first manner. This function effectively checks if the sequence of leaf values in both trees are identical by following these steps:

1. Define a helper function explore to traverse each tree recursively. Pass each node and an empty array to store leaf values.
2. In the explore function:
   • Check if a node exists; if not, return immediately.
   • Determine if the node is a leaf (i.e., has no left or right children). If it is, push the node's value to the leafVals array.
   • Recursively visit the left and then the right child of the current node.
3. Initialize two empty arrays, leafList1 and leafList2, to hold the leaf values of rootA and rootB respectively.
4. Invoke explore on both rootA and rootB, using leafList1 and leafList2 to collect their leaf values.
5. Compare the two leaf arrays:
   • Check if they have the same length.
   • Use the .every() method to check if every corresponding pair of values in the two arrays are the same.

The function finally returns true if both conditions are satisfied, otherwise false. This method efficiently checks leaf similarity using direct comparison of leaf sequences, ensuring both structure and value equality for leaf nodes in both trees.

class Solution:
    def similarLeaf(self, tree1, tree2):
        def traverse(n):
            if n:
                if not n.left and not n.right:
                    yield n.val
                yield from traverse(n.left)
                yield from traverse(n.right)

        return list(traverse(tree1)) == list(traverse(tree2))

The provided Python solution defines a method to determine if two binary trees are leaf-similar. Leaf-similar trees contain leaves, when considered from left to right, forming the same sequence. The solution comprises a nested traverse function, which makes use of a generator to yield leaf nodes' values.

• To achieve this:

1. Define a nested traverse function inside the similarLeaf method. traverse uses recursion to navigate through the tree.
2. The traverse function checks if a node is non-null and if it has no children (making it a leaf), then yields its value.
3. Recursion continues down to the left child and then the right child of the node, using yield from to handle the recursive yields.
4. In the similarLeaf method, convert the yielded values from both trees into lists and compare them using equality.

This method efficiently compares the leaves of both trees without needing extra space for storing non-leaf nodes and directly compares the sequences once generated. Ensure to pass the root of both trees when initializing and calling this class method.