LeetCode 872. Leaf-Similar Trees

872. Leaf-Similar Trees

 

Problem

---

Solution

The key requirement of this problem is as follows:

1. Return True if the leaf of sequences of root1 and root2 are the same otherwise return False.

To satisfy this requirement, I used a preorder traversal with a stack.

 

Since we need to process two binary trees, I created a helper function getLeaves.

 

First, initialize stack as a list containing root, and set leaves as an empty list.

 

If root is None, return leaves because the tree is empty.

 

While stackis not empty, do the following steps:

1. Pop the last node from stack.
2. If the current node has no left and right children, append its value to leaves.
3. Otherwise, if the node has a right child, append it to stack.
4. If the node has a left child, append it to stack.

By pushing the right child first, the left subtree is processed first.

This keeps the leaf order consistent with a preorder traversal.

 

At the end of the loop, return the leaves.

 

Outside of getLeaves, call it for both trees and compare the results.
If both leaf lists are the same, return True otherwise return False.

 

class Solution(object):
    def leafSimilar(self, root1, root2):
        def getLeaves(root):
            stack = [root]
            leaves = []
            if not stack:
                return leaves

            while stack:
                node = stack.pop()
                if not node.left and not node.right:
                    leaves.append(node.val)
                else:
                    if node.right:
                        stack.append(node.right)
                    if node.left:
                        stack.append(node.left)

            return leaves

        tree1 = getLeaves(root1)
        tree2 = getLeaves(root2)
        return tree1 == tree2

 

---

 

https://github.com/K-MarkLee/LeetCode-Practice

GitHub - K-MarkLee/LeetCode-Practice: A collection of LeetCode questions to ace the coding interview! - Created using [LeetHub 2