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.

Question

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

Example:

Input: {1,#,2,3}, {1,2,#,3}
Output: 
Explaination: 
the first tree:
  1
    \                
     2                
    /                 
   3   
the second tree:
    1
   /
  2
 /
3
The leaf value sequence is: [3], so the same


Input: {1,#,2,3}, {1,2,#,3}
Output: 
Explaination: 
the first tree:
  1
    \                
     2                
    /                 
   3   
the second tree:
   1
  / \                
 2   3    
The first leaf value sequence is: [3], the second tree is: [2, 3], so it is not the same

Analyzation

Recursion

Simple problem. If the node has no children, append that val to the corresponding list and do the same thing for the other tree.

The Code

class Solution:
    """
    @param root1: the first tree
    @param root2: the second tree
    @return: returns whether the leaf sequence is the same
    """
    def leafSimilar(self, root1, root2):
        # write your code here.
        if root1 is None or root2 is None:
            return False
        
        result1 = []
        result2 = []
            
        self.dfs(root1, result1)
        self.dfs(root2, result2)
        
        return result1 == result2
    
    
    def dfs(self, node, result):
        if node is None:
            return
        
        self.dfs(node.left, result)
        self.dfs(node.right, result)
            
        if node.left is None and node.right is None:
            result.append(node.val)
            return

Time & Space Complexity

• Time complexity: O(n). Remember that the best case of a Binary Tree is O(logn) since it is a balanced tree but the worst case is O(n) because it can skew to only one side.
• Space complexity: O(n). Remember that the space complexity is always about how many nodes there are in a Binary Tree. If the tree is well-balanced then it is O(logn) but the worst case will be O(n).