Leaf-Similar Trees

Problem Id: 872 Difficulty: Easy Tag: Tree Tag: Depth-first Search


Intuition

Use a DFS to get all leaves of a node. And then, we could simply compare the leaves of 2 tree.

Solution


# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def leafSimilar(self, root1: TreeNode, root2: TreeNode) -> bool:
        leaves1 = []
        leaves2 = []
        self._dfs_get_leaf(root1, leaves1)
        self._dfs_get_leaf(root2, leaves2)
        if len(leaves1) != len(leaves2):
            return False
        for p, q in zip(leaves1, leaves2):
            if p != q:
                return False
        return True

    def _dfs_get_leaf(self, node, leaves):
        if node is None:
            return
        if node.left is None and node.right is None:
            leaves.append(node.val)
        else:
            self._dfs_get_leaf(node.left, leaves)
            self._dfs_get_leaf(node.right, leaves)