Leaf-Similar Trees

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    private void traverse(TreeNode root, List<Integer> list) {
18        if (root == null) {
19            return;
20        }
21
22        if (root.left == null && root.right == null) {
23            list.add(root.val);
24            return;
25        }
26
27        traverse(root.left, list);
28        traverse(root.right, list);
29    }
30    public boolean leafSimilar(TreeNode root1, TreeNode root2) {
31        List<Integer> list1 = new LinkedList<Integer>();
32        List<Integer> list2 = new LinkedList<Integer>();
33        traverse(root1, list1);
34        traverse(root2, list2);
35
36        System.out.println(list1);
37        System.out.println(list2);
38        if (list1.size() != list2.size()) {
39            return false;
40        }
41
42        for (int i = 0; i < list1.size(); i++) {
43            // Note: in Java you should not use == when you compare objects of
44            // a class that wraps a primitive type. You would be comparing a
45            // reference instead of the actual value.
46            if (!list1.get(i).equals(list2.get(i))) {
47                return false;
48            }
49        }
50
51        return true;
52    }
53}
54
55
56// iterative approach
57// class Solution {
58//     private void traverse(TreeNode root, List<Integer> list) {
59//         Stack<TreeNode> stack = new Stack<TreeNode>();
60//         stack.push(root);
61//         while (!stack.isEmpty()) {
62//             TreeNode curr = stack.pop();
63
64//             if (curr.left == null && curr.right == null) {
65//                 list.add(curr.val);
66//             }
67//             if (curr.left != null) {
68//                 stack.push(curr.left);
69//             }
70//             if (curr.right != null) {
71//                 stack.push(curr.right);
72//             }
73//         }
74//     }
75//     public boolean leafSimilar(TreeNode root1, TreeNode root2) {
76//         List<Integer> list1 = new LinkedList<Integer>();
77//         List<Integer> list2 = new LinkedList<Integer>();
78//         traverse(root1, list1);
79//         traverse(root2, list2);
80
81//         System.out.println(list1);
82//         System.out.println(list2);
83//         if (list1.size() != list2.size()) {
84//             return false;
85//         }
86
87//         for (int i = 0; i < list1.size(); i++) {
88//             if (list1.get(i).intValue() != list2.get(i).intValue()) {
89//                 return false;
90//             }
91//         }
92
93//         return true;
94//     }
95// }