This question is in reference to leetcode problem 872, Leaf-Similar Trees. I had no issue with the problem, but afterwards I wanted to use strings as opposed to a linked list. For reference here is my solution:
class Solution {
public boolean leafSimilar(TreeNode root1, TreeNode root2) {
LinkedList<Integer> l1 = new LinkedList<>();
LinkedList<Integer> l2 = new LinkedList<>();
traverse(root1,l1);
traverse(root2, l2);
if(l1.size()!=l2.size())
return false;
for(int i=0;i<l1.size();i++)
if(l1.get(i)!=l2.get(i))
return false;
return true;
}
public void traverse(TreeNode node, LinkedList ll){
if(node==null)
return;
if(node.left==null&&node.right==null)
{
ll.add(node.val);
return;
}
traverse(node.left,ll);
traverse(node.right,ll);
}
}
I wondered if I could cut down lines by using strings instead of linked lists, adding each end node value to a string and then comparing the strings with .equals for a 1 line comparison.
class Solution {
public boolean leafSimilar(TreeNode root1, TreeNode root2) {
String s1 = "";
String s2 = "";
traverse(root1,s1);
traverse(root2,s2);
return s1.equals(s2);
}
public void traverse(TreeNode node, String s){
if(node==null)
return;
if(node.left==null&&node.right==null)
{
s = s+node.val;
return;
}
traverse(node.left,s);
traverse(node.right,s);
}
}
This failed solution ends up just comparing two empty strings. What I realized was that the strings do not update their values the same way the linked lists did. Both the strings and linked lists were local to the first method, yet the linked list within leafSimilar had values added as an effect of the traverse method while strings didn't. I thought this had to do with the fact that strings are immutable in java yet it also didn't work for stringbuilder. If the string is made global within the class and thus not passed as a parameter to traverse this works, though it fails the final test case, but that isn't important to my question. Can someone explain what is happening differently between the lists and the strings?
