[Java] Leetcode 652. Find Duplicate Subtrees [Binary Tree #10]

[@suryateja6780]

What is that chrome extension you are using to draw/write on the tab?

[@pengx9000]

I'm a little bit confused about this: if we do post-order traversal, why we first append the curNode val (line 44), then append left subtree, last right subtree (15:00), shouldn't be (Left, Right, CurNode)?

[@ovidiubalaban2466]

It doesn't matter because it's just a String representation which is used to compare values, and it's the same if the CurNode is at the start or at end, you could try it and you will see that it works in both ways. What it does matter is to execute first, the leftNode, then the rightNode, and then to return the curSubtree.

[@MeetManga]

Another solution，the time complexity and space complexity is also N²， but the code is shorter, enjoy:
class Solution {
Map map = new HashMap();
List res = new LinkedList();
public List findDuplicateSubtrees(TreeNode root) {
String path = "";
dfs(root, path);
return res;
}
private String dfs(TreeNode root, String path){
if(root == null) return "#";
path += String.join(",", String.valueOf(root.val),
dfs(root.left, path),
dfs(root.right, path));
map.put(path, map.getOrDefault(path, 0) + 1);
if(map.get(path) == 2){
res.add(root);
}
return path;
}
}

[@xuebindong4803]

love you

[@diwyanshukanthwal8669]

why inorder will not work on this

[@austing.8682]

Because you need the left serialization and the right serialization before you can create a complete a serialization for the current node.

[@rahulmg05]

@@austing.8682 Isn't that true for pre order and post order as well ?