LeetCode: Leaf-similar trees C# Please comment about performance

https://leetcode.com/problems/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.
  
  Note:
  
  Both of the given trees will have between 1 and 100 nodes.


using System.Collections.Generic;
using GraphsQuestions;
using Microsoft.VisualStudio.TestTools.UnitTesting;

namespace TreeQuestions
{
    /// &lt;summary&gt;
    /// https://leetcode.com/problems/leaf-similar-trees/
    /// &lt;/summary&gt;
    [TestClass]
    public class LeafSimilarTrees
    {
        [TestMethod]
        public void LeafSimilarTreesTest()
        {
            TreeNode root1 = new TreeNode(3);
            root1.left = new TreeNode(5);
            root1.left.left = new TreeNode(6);
            root1.left.right = new TreeNode(2);
            root1.left.right.left = new TreeNode(7);
            root1.left.right.right = new TreeNode(4);
            root1.right = new TreeNode(1);
            root1.right.left = new TreeNode(9);
            root1.right.right = new TreeNode(8);

            TreeNode root2 = new TreeNode(3);
            root2.left = new TreeNode(1);
            root2.left.left = new TreeNode(6);
            root2.left.right = new TreeNode(2);
            root2.left.right.left = new TreeNode(7);
            root2.left.right.right = new TreeNode(4);
            root2.right = new TreeNode(5);
            root2.right.left = new TreeNode(9);
            root2.right.right = new TreeNode(8);
            Assert.IsTrue(LeafSimilar(root1,root2));

        }

        public bool LeafSimilar(TreeNode root1, TreeNode root2)
        {
            List&lt;int&gt; tree1 = new List&lt;int&gt;();
            List&lt;int&gt; tree2 = new List&lt;int&gt;();
            DFS(root1, tree1);
            DFS(root2, tree2);
            if (tree1.Count != tree2.Count)
            {
                return false;
            }
            for (int i = 0; i &lt; tree1.Count; i++)
            {
                if (tree1[i] != tree2[i])
                {
                    return false;
                }
            }
            return true;
        }

        public void DFS(TreeNode root, List&lt;int&gt; list)
        {
            if (root == null)
            {
                return;
            }
            if (root.left != null)
            {
                DFS(root.left, list);
            }
            if (root.right != null)
            {
                DFS(root.right, list);
            }
            if (root.left == null &amp;&amp; root.right == null)
            {
                list.Add(root.val);
            }
        }
    }
}
There's a problem with your approach: it always visits all nodes to build value lists, even when the trees aren't similar at all. By obtaining leaf-node values lazily, you'll prevent a lot of unnecessary traversal work if the trees are different.

This can be achieved by changing DFS to a generator method (using yield), and comparing the results with SequenceEqual, as janos already pointed out. You'll want to use an explicit stack instead of recursion though, to avoid incurring too much overhead.

However, for trees that are leaf-similar, the added overhead ends up making things slower. The fastest approach is probably a recursive method that does a depth-first traversal of both trees at the same time, bailing out as soon as it finds a leaf-node difference.