Problem of The Day: Leaf-Similar Trees

Problem Statement

leetcode problem link

My Solution [Accepted]

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    public List<int> arr1 { get; set;} = new List<int>();
    public List<int> arr2 { get; set;} = new List<int>();
    public void PreorderTraversal(TreeNode root, List<int> res) {
        if (root is null)
            return;
        if (root.left is null && root.right is null) {
            res.Add(root.val);
            return;
        }
        PreorderTraversal(root.left, res);
        PreorderTraversal(root.right, res);
    }

    public bool LeafSimilar(TreeNode root1, TreeNode root2) {
        PreorderTraversal(root1, arr1);
        PreorderTraversal(root2, arr2);
        if (arr1.Count != arr2.Count)
            return false;
        var length = arr1.Count;
        for (int i = 0; i < length; i++) {
            if (arr1[i] != arr2[i]) {
                return false;
            }
        }
        return true;
    }
}

Improve Code

public class Solution {
    private void CollectLeaves(TreeNode root, List<int> leaves) {
        if (root == null) return;

        if (root.left == null && root.right == null) {
            leaves.Add(root.val);
            return;
        }

        CollectLeaves(root.left, leaves);
        CollectLeaves(root.right, leaves);
    }

    public bool LeafSimilar(TreeNode root1, TreeNode root2) {
        var leaves1 = new List<int>();
        var leaves2 = new List<int>();

        CollectLeaves(root1, leaves1);
        CollectLeaves(root2, leaves2);

        if (leaves1.Count != leaves2.Count)
            return false;

        for (int i = 0; i < leaves1.Count; i++) {
            if (leaves1[i] != leaves2[i])
                return false;
        }

        return true;
    }
}

Optimize code - Without storing in list

public class Solution {
    private IEnumerable<int> GetLeaves(TreeNode root) {
        if (root == null)
            yield break;

        if (root.left == null && root.right == null) {
            yield return root.val;
            yield break;
        }

        foreach (var v in GetLeaves(root.left))
            yield return v;

        foreach (var v in GetLeaves(root.right))
            yield return v;
    }

    public bool LeafSimilar(TreeNode root1, TreeNode root2) {
        using var e1 = GetLeaves(root1).GetEnumerator();
        using var e2 = GetLeaves(root2).GetEnumerator();

        while (true) {
            bool m1 = e1.MoveNext();
            bool m2 = e2.MoveNext();

            if (m1 != m2)
                return false;

            if (!m1) // both ended
                return true;

            if (e1.Current != e2.Current)
                return false;
        }
    }
}

Editorial

Approach 1: Depth First Search

class Solution:
    def leafSimilar(self, root1, root2):
        def dfs(node):
            if node:
                if not node.left and not node.right:
                    yield node.val
                yield from dfs(node.left)
                yield from dfs(node.right)

        return list(dfs(root1)) == list(dfs(root2))