872.-leaf-similar-trees.md

872. 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.

  

• 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.

• https://leetcode.com/problems/leaf-similar-trees/

Solution 1

Runtime: 28 msMemory Usage: 14.2 MB

class Solution:
    def leafSimilar(self, root1, root2):
        return self.iterative(root1,[]) == self.iterative(root2,[])
        
    def iterative(self,root,s):
        if root is not None:
            stack = []
            stack.append(root)
            while stack:
                x = stack.pop(-1)
                if x.left is None and x.right is None:
                    s.append(x.val)
                    continue
                if x.right is not None:
                    stack.append(x.right)
                if x.left is not None:
                    stack.append(x.left)
        return s

{% hint style="info" %} Defined a method to test. The method works by looking for the leaves and recording a list of leaves. {% endhint %}