872. 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.

Code:

I create 2 stacks and use DFS in using post-order traversal. In the DFS helper function it only returns the button value when left and right sub-nodes are empty, and do then the comparison.

If both the values are not match, it returns false. In the end we return !any() to make sure both the stacks are empty.

public class Solution {
    public bool LeafSimilar(TreeNode root1, TreeNode root2) {
        Stack<TreeNode> stack1 = new Stack<TreeNode>();
        Stack<TreeNode> stack2 = new Stack<TreeNode>();
        stack1.Push(root1);
        stack2.Push(root2);
        while(stack1.Any() && stack2.Any())
            if(dfs(stack1) != dfs(stack2))
                return false;
        return !stack1.Any() && !stack2.Any();
    }


private int dfs(Stack<TreeNode> s)
    {
        while(true)
        {
            TreeNode node = s.Pop();
            if(node.right != null) s.Push(node.right);
            if(node.left != null) s.Push(node.left);
            if(node.left == null && node.right == null) return node.val;
        }
    }
}