[LeetCode] Leaf-Similar Trees

Problem: 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.

Example:

Input: root1 = [3,5,1,6,2,9,8,null,null,7,4], root2 = [3,5,1,6,7,4,2,null,null,null,null,null,null,9,8]
Output: true

Input: root1 = [1,2,3], root2 = [1,3,2]
Output: false

Approach: We can use pre order traversal to store all the leaf in a list. We will run this traversal for both the trees and in the end we will compare both these lists. If these lists are same then we return true; false otherwise.

Implementation in C#:

    public bool LeafSimilar(TreeNode root1, TreeNode root2)

    {

        var leafSq1 = new List<int>();

        var leafSq2 = new List<int>();

        this.GetLeafSequence(root1, leafSq1);

        this.GetLeafSequence(root2, leafSq2);

        return leafSq1.SequenceEqual(leafSq2);

    }

    private void GetLeafSequence(TreeNode node, List<int> result)

    {

        if (node == null)

        {

            return;

        }

        if (node.left == null && node.right == null)

        {

            result.Add(node.val);

            return;

        }

        this.GetLeafSequence(node.left, result);

        this.GetLeafSequence(node.right, result);

    }

Complexity: O(n)