Consider all the leaves of a binary tree, from&nbsp;left to right order, the values of those&nbsp;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&nbsp;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.

&nbsp;
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


&nbsp;
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].


# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def leafSimilar(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:
        tree=[]
        def inorder(root):
            nonlocal tree
            if root is None:
                return
            if root.left is None and root.right is None:
                tree.append(root.val)
            
            inorder(root.left)
            inorder(root.right)
        
        inorder(root1)
        inorder(root2)
        tree1=tree[:len(tree)//2]
        tree2=tree[len(tree)//2:]
        if tree1==tree2:
            return True
        else:
            return False
class Solution {
    public boolean leafSimilar(TreeNode root1, TreeNode root2) {
        List<Integer> list1 = new ArrayList<>();
        checkLeaf(root1, list1);
        List<Integer> list2 = new ArrayList<>();
        checkLeaf(root2, list2);

        if(list1.size() != list2.size()) return false;

        int i = 0;
        while(i < list1.size()){
            if(list1.get(i) != list2.get(i)){
                return false;
            }
            i++;
        }
        return true;
    }

    private void checkLeaf(TreeNode node, List<Integer> arr){
        if(node.left == null && node.right == null) arr.add(node.val);
        if(node.left != null) checkLeaf(node.left, arr);
        if(node.right != null) checkLeaf(node.right, arr);
    }
}
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    
    /*  How to get LeafOrder?
        Simply traverse the tree Left->right
        whenever you get a leaf, push its value to a vector
    */
    
    
    void getLeafOrder(TreeNode* root, vector<int> &leafOrder){  // Here we are passing vector
        if(root == NULL){                                       // by reference to make changes
            return;                                             // directly in main vector
        }
        
        // Leaf found -> push its value in the vector
        if(root->left == NULL and root->right == NULL){
            leafOrder.push_back(root->val);
            return;
        }
        
        getLeafOrder(root->left, leafOrder);    // Left then Right -> to maintain the sequence
        getLeafOrder(root->right, leafOrder);
    }
    
    
    bool leafSimilar(TreeNode* root1, TreeNode* root2) {
        vector<int> leafOrder1;
        vector<int> leafOrder2;
        
        getLeafOrder(root1, leafOrder1);    // Get leaf order for both trees
        getLeafOrder(root2, leafOrder2);
        
        return leafOrder1 == leafOrder2;    // return if they are equal or not
    }
};
/*
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root1
 * @param {TreeNode} root2
 * @return {boolean}
 */
 
var leafSimilar = function(root1, root2) {
    let array1 = [], array2 = [];
    let leaf1 = getLeaf(root1, array1),
        leaf2 = getLeaf(root2, array2);
    
    if (leaf1.length !== leaf2.length){   // if different lengths, return false right away
        return false;
    } 
    
    for(let i = 0; i < leaf1.length; i++){
        if (leaf1[i] !== leaf2[i]){     // compare pair by pair
            return false;
        }
    }
	
    return true;
};

var getLeaf = function(root, array){    // DFS
    if (!root){
        return;
    }
    if (!(root.left || root.right)){
        array.push(root.val);  // push leaf value to the array
    }
    getLeaf(root.left, array);
    getLeaf(root.right, array);
    
    return array;
}
Leaf-Similar Trees