872. Leaf-Similar Trees

Version #2 Only Stack Space[TODO]
I don't think it is necessary to do so


Version #1 Straightforward
Time O(N1 + N2)
Space O(N1 + N2) -> size of leaves is about N / 2

98.60 %
class Solution {
    public boolean leafSimilar(TreeNode root1, TreeNode root2) {
        if (root1 == null & root2 == null) return true;
        if (root1 == null || root2 == null) return false;
        Queue<Integer> que = new LinkedList<>();
       
        dfs1(root1, que);
        return dfs2(root2, que);
    }
    private void dfs1(TreeNode node, Queue<Integer> que) {
        if (node.left == null && node.right == null) {
            que.offer(node.val);
            return;
        }
        if (node.left != null) {
            dfs1(node.left, que);
        }
        if (node.right != null) {
            dfs1(node.right, que);
        }
    }
   
    private boolean dfs2(TreeNode node, Queue<Integer> que) {
        if (node.left == null && node.right == null) {
            if (!que.isEmpty() && node.val == que.poll()) {
                return true;
            }
            return false;
        }
        return (node.left == null || dfs2(node.left, que))
            && (node.right == null || dfs2(node.right, que));
    }
}