Leaf-Similar Trees

• Initialize two empty lists, leaves1 and leaves2.
• Define a recursive DFS helper function getLeaves(node, list).
• In getLeaves, if node is null, return.
• If node is a leaf (node.left == null && node.right == null), add node.val to the list.
• Recursively call getLeaves for the left child: getLeaves(node.left, list).
• Recursively call getLeaves for the right child: getLeaves(node.right, list).
• Call getLeaves(root1, leaves1) to populate the first list.
• Call getLeaves(root2, leaves2) to populate the second list.
• Return the result of comparing leaves1 and leaves2 for equality.

We define a helper function, say getLeaves, that takes a tree node and a list as input. This function will traverse the tree starting from the given node. The traversal can be pre-order, in-order, or post-order; the key is to visit children in a consistent order (left then right) to maintain the left-to-right sequence of leaves. Inside the getLeaves function, we check if the current node is a leaf (i.e., it has no left and no right child). If it is, we add its value to the list. The main function leafSimilar initializes two empty lists. It then calls getLeaves for root1 and the first list, and then for root2 and the second list. Finally, it compares the two populated lists. If they are identical in content and order, the trees are leaf-similar, and we return true; otherwise, false.

1/**2 * Definition for a binary tree node.3 * public class TreeNode {4 *     int val;5 *     TreeNode left;6 *     TreeNode right;7 *     TreeNode() {}8 *     TreeNode(int val) { this.val = val; }9 *     TreeNode(int val, TreeNode left, TreeNode right) {10 *         this.val = val;11 *         this.left = left;12 *         this.right = right;13 *     }14 * }15 */16class Solution {17    public boolean leafSimilar(TreeNode root1, TreeNode root2) {18        List<Integer> leaves1 = new ArrayList<>();19        List<Integer> leaves2 = new ArrayList<>();20        getLeaves(root1, leaves1);21        getLeaves(root2, leaves2);22        return leaves1.equals(leaves2);23    }24 25    private void getLeaves(TreeNode node, List<Integer> leafValues) {26        if (node == null) {27            return;28        }29        if (node.left == null && node.right == null) {30            leafValues.add(node.val);31        }32        getLeaves(node.left, leafValues);33        getLeaves(node.right, leafValues);34    }35}

• Initialize two stacks, s1 and s2, and push root1 and root2 onto them, respectively.
• Create a helper function findNextLeaf(stack) that finds and returns the value of the next leaf.
• Inside findNextLeaf, loop while the stack is not empty:
  • Pop a node from the stack.
  • If the node has a right child, push it onto the stack.
  • If the node has a left child, push it onto the stack. (This order ensures left-to-right traversal).
  • If the node is a leaf, return its value.
• In the main function, loop while both s1 and s2 are not empty.
• Inside the loop, call findNextLeaf(s1) and findNextLeaf(s2) and compare their results. If they are not equal, return false.
• After the loop, check if both stacks are empty. If they are, it means both leaf sequences were identical and have been fully traversed. Return true. Otherwise, one sequence was longer than the other, so return false.

Instead of a recursive DFS, we use a stack for an iterative pre-order traversal. This allows us to 'pause' the traversal after finding a leaf and 'resume' it later to find the next one. We create a helper function, findNextLeaf, which takes a stack (representing the state of the traversal for one tree) and finds the next leaf value. The findNextLeaf function works in a loop: it pops a node from the stack. If the node is a leaf, its value is returned. If it's not a leaf, its children are pushed onto the stack (right child first, then left child) to ensure the left-to-right pre-order traversal. The main function leafSimilar initializes two stacks, one for each tree, pushing the respective roots. It then enters a loop, calling findNextLeaf for both stacks in each iteration to get the next pair of leaves. If the leaf values differ, it immediately returns false. If one sequence ends before the other, it also returns false. If both sequences end at the same time (both findNextLeaf calls indicate no more leaves), it returns true.

1/**2 * Definition for a binary tree node.3 * public class TreeNode {4 *     int val;5 *     TreeNode left;6 *     TreeNode right;7 *     TreeNode() {}8 *     TreeNode(int val) { this.val = val; }9 *     TreeNode(int val, TreeNode left, TreeNode right) {10 *         this.val = val;11 *         this.left = left;12 *         this.right = right;13 *     }14 * }15 */16class Solution {17    public boolean leafSimilar(TreeNode root1, TreeNode root2) {18        Stack<TreeNode> s1 = new Stack<>();19        Stack<TreeNode> s2 = new Stack<>();20        if (root1 != null) s1.push(root1);21        if (root2 != null) s2.push(root2);22        23        while (!s1.isEmpty() && !s2.isEmpty()) {24            if (findNextLeaf(s1) != findNextLeaf(s2)) {25                return false;26            }27        }28        29        return s1.isEmpty() && s2.isEmpty();30    }31 32    private int findNextLeaf(Stack<TreeNode> stack) {33        while (true) {34            TreeNode node = stack.pop();35            if (node.right != null) {36                stack.push(node.right);37            }38            if (node.left != null) {39                stack.push(node.left);40            }41            if (node.left == null && node.right == null) {42                return node.val;43            }44        }45    }46}