872. Leaf‐Similar Trees - cocoder39/coco39_LC GitHub Wiki

872. Leaf-Similar Trees

solution 1 is easy but the the optimization (option 2 and 3 are upper mid)

Initial Solution: DFS

Optimization: instead of collecting all leaves then do comparison, can we compare incrementally. eg get a pair of leaves, compare, then get another pair of leaves

class Solution:
    def leafSimilar(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:
        res1 = self.dfs(root1)
        res2 = self.dfs(root2)

        if len(res1) != len(res2):
            return False

        for val1, val2 in zip(res1, res2):
            if val1 != val2:
                return False
        return True
    

    def dfs(self, root):
        if not root:
            return []
        
        if not root.left and not root.right:
            return [root.val]
        
        res = []
        if root.left:
            res.extend(self.dfs(root.left))
        if root.right:
            res.extend(self.dfs(root.right))
        return res

solution 2: use a stack to mimic dfs and get one leave node each time

class Solution:
    def leafSimilar(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:
        
        def getLeave(stack):
            while stack:
                cur = stack.pop()
                if not cur.left and not cur.right:
                    return cur.val

                # append right then left so left could be popped out first to be processed 
                if cur.right:
                    stack.append(cur.right)
                if cur.left:
                    stack.append(cur.left)
            # no more leave
            return None
        
        stack1, stack2 = [], []
        if root1:
            stack1.append(root1)
        if root2:
            stack2.append(root2)
        
        while stack1 and stack2:
            leave1 = getLeave(stack1)
            leave2 = getLeave(stack2)
            if leave1 != leave2:
                return False
        
        return not stack1 and not stack2

solution 3: extend recursive DFS with using python generator

class Solution:
    def leafSimilar(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:
        
        def getNextLeafGenerator(node):
            if node:
                if not node.left and not node.right:
                    yield node.val
                if node.left:
                    # yield from to delegate to sub-generator 
                    yield from getNextLeafGenerator(node.left)
                if node.right:
                    yield from getNextLeafGenerator(node.right)
        
        gen1 = getNextLeafGenerator(root1)
        gen2 = getNextLeafGenerator(root2)
        while True:
            # default to None to avoid StopIteration exception
            leaf1 = next(gen1, None)
            leaf2 = next(gen2, None)

            if leaf1 != leaf2:
                return False
            if leaf1 is None and leaf2 is None:
                return True
        return False