Blogs Hub

by Sumit Chourasia | Oct 09, 2020 | Category :coding | Tags : algorithm binary-tree data-structure easy leetcode tree

Leaf-Similar Trees - Tree - Easy - LeetCode

Leaf-Similar Trees - Tree - Easy - LeetCode

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], root2 = [1]
Output: true
Example 3:

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

Input: root1 = [1,2], root2 = [2,2]
Output: true
Example 5:


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

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    List<int> leaf1 = new List<int>();
    List<int> leaf2 = new List<int>();
    public bool LeafSimilar(TreeNode root1, TreeNode root2) {
        Helper(root1,true);
        Helper(root2,false);
        
        if(leaf1.Count()!=leaf2.Count()){
            return false;
        }
        for(int i=0;i<leaf1.Count();i++){
            if(leaf1[i]!=leaf2[i]){
                return false;
            }
        }
        
        return true;
    }
    
    private void Helper(TreeNode root, bool isLeftTree){
        if(root==null){
            return;
        }
        if(root.left==null && root.right == null){
            if(isLeftTree){
                leaf1.Add(root.val);
            }
            else{
                leaf2.Add(root.val);
            }
        }
        Helper(root.left,isLeftTree);
        Helper(root.right,isLeftTree);
    }
}

Time Complexity: O(n)

Space Complexity: O(1)