Verbose Java solution, tree traversal


  • 3

    Idea is to traverse the tree and serialize each sub-tree to a string and put them into a HashMap. The first time we put null as the value and later we put the real node as the value. Then at last, every entry in the map with not null value, is an answer.
    An optimization is to start searching from the first possible start node which has both left and right sub-trees. Think about why tree node with only one sub-tree can't be a valid start point?

    public class Solution {
        Map<String, TreeNode> map = new HashMap<>();
        
        public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
            List<TreeNode> result = new ArrayList<>();
            if (root == null) return result;
            
            traverse(first(root));
            
            for (TreeNode node : map.values()) {
                if (node != null) {
                    result.add(node);
                }
            }
            
            return result;
        }
        
        private TreeNode first(TreeNode root) {
            if (root == null) return null;
            if (root.left != null && root.right != null) return root;
            if (root.left != null) return first(root.left);
            return first(root.right);
        }
        
        private void traverse(TreeNode root) {
            if (root == null) return;
            
            String s = path(root);
            if (map.containsKey(s)) {
                map.put(s, root);
            }
            else {
                map.put(s, null);
            }
            
            traverse(root.left);
            traverse(root.right);
        }
        
        private String path(TreeNode root) {
            if (root == null) return "#";
            return root.val + "," + path(root.left) + "," + path(root.right);
        }
    }
    

  • 0

    Well, I do not think it is sort of "Verbose". You encode the path into a string. Good Solution.


  • 0
    Z
    This post is deleted!

  • 0
    Z
    This post is deleted!

  • 0

    @zestypanda Thanks for pointing out. Fixed.


  • 0
    D

    Your path method:

        private String path(TreeNode root) {
            if (root == null) return "#";
            return root.val + "," + path(root.left) + "," + path(root.right);
        }
    

    This is pre-order traversal, right?
    Trees that have the same pre-order sequence aren't necessarily identical.
    Could you tell me how your solution addressed this problem?


  • 0

    @dkonayuki said in Verbose Java solution, tree traversal:

    Your path method:

        private String path(TreeNode root) {
            if (root == null) return "#";
            return root.val + "," + path(root.left) + "," + path(root.right);
        }
    

    This is pre-order traversal, right?
    Trees that have the same pre-order sequence aren't necessarily identical.
    Could you tell me how your solution addressed this problem?

    Could you provide an example?


  • 0
    D

    I believe @shawngao was referring to the fact that for "in-order" traversal and uniqueness ,as the question asks, your return needs to be left - node - right rather than node - left - right.

    Would duplicate paths be only represented once since the key would be the same?


  • 0
    D

    @shawngao
    Hmm, look like your path method is pre-order traversal with 'marker' for null nodes.
    It's indeed unique within the trees.
    I was confused with the traditional pre-order traversal which does not uniquely represent a tree.


  • 0
    public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
        Map<String, TreeNode> dup = new HashMap<>();
        List<TreeNode> result = new ArrayList<>();
        traverse(root, dup);
        
        //return dup.values().stream().filter(a -> a!=null).collect(Collectors.toList());
        for(TreeNode e : dup.values()) if(e != null) result.add(e);
        return result;
    }
    private String traverse(TreeNode root, Map<String, TreeNode> dup) {
        if(root == null) return "#";
        String serializedTree = root.val + traverse(root.left, dup) + traverse(root.right, dup);
    
        if(dup.containsKey(serializedTree)) dup.put(serializedTree, root);
        else dup.put(serializedTree, null);
        
        return serializedTree;
    }

  • 0

    @shawngao said in Verbose Java solution, tree traversal:

    Could you provide an example?

    The uniqueness of the serialized key is hard to either prove or negate without a careful analysis. I feel like it would work, but not confident indeed.

    @dkonayuki I'm curious how you later find out it's unique. Because IMHO not being strictly pre-order doesn't necessary mean it's unique. Do I miss something here?


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.