Java Concise Postorder Traversal Solution


  • 38
    public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
        List<TreeNode> res = new LinkedList<>();
        postorder(root, new HashMap<>(), res);
        return res;
    }
    
    public String postorder(TreeNode cur, Map<String, Integer> map, List<TreeNode> res) {
        if (cur == null) return "#";  
        String serial = cur.val + "," + postorder(cur.left, map, res) + "," + postorder(cur.right, map, res);
        if (map.getOrDefault(serial, 0) == 1) res.add(cur);
        map.put(serial, map.getOrDefault(serial, 0) + 1);
        return serial;
    }
    

  • 0
    J

    @compton_scatter Similar code in C# gave runtime error for me. I should have coded in java


  • 4

    @compton_scatter sorry, why postorder?


  • 0
    K

    @JkApacc same!


  • 0
    X

    Very good solution!
    I put a isSameTree API there and got TLE.

    private boolean isSameTree(TreeNode n1, TreeNode n2) {
        if (n1 == null && n2 == null)
          return true;
        if (n1 == null || n2 == null || n1.val != n2.val)
          return false;
        return isSameTree(n1.left, n2.left) && isSameTree(n1.right, n2.right);
      }
    

  • 8
    V

    it seems to be pre-order?


  • 0
    S
    public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
            List<TreeNode> result = new LinkedList<>();
            Map<String,Integer> map = new HashMap<>();
            findDuplicateSubtreesHelperPostOrder(map,root,result);
    
            return result;
    
        }
        public String findDuplicateSubtreesHelperPostOrder(Map<String,Integer> map,TreeNode root,List<TreeNode> result){
            if(root==null)
                return "#";
            String path = root.val + findDuplicateSubtreesHelperPostOrder(map,root.left,result) + findDuplicateSubtreesHelperPostOrder(map,root.right,result);
            Integer times = map.getOrDefault(path,0);
            if(times==1){
                result.add(root);
            }
            map.put(path,times+1);
            return path;
        }
    

  • 0

    @vincexu It is postorder (we process left and right subtrees before processing the current one)


  • 0
    X

    Yeah, it's easy to be confused here. The string serial won't be ready after finishing both left and right recursion.

        String serial = cur.val + "," + postorder(cur.left, map, res) + "," + postorder(cur.right, map, res);
    

  • 2
    Z

    Actually, I think only post order couldn't decide the structure of a tree.


  • 0
    P

    The postOrder function can be simplified by

    public String postorder(TreeNode cur, Map<String, Integer> map, List<TreeNode> res) {
            if (cur == null) 
                return "#";  
            String serial = cur.val + "," + postorder(cur.left, map, res) + "," + postorder(cur.right, map, res);
            if (map.getOrDefault(serial, 0) == 1) 
                res.add(cur);
            map.put(serial, map.getOrDefault(serial, 0) + 1);
            return serial;
        }

  • 0
    S

    @JkApacc You got runtime error due to a too deep recursion on test case like [0,null,0,null.....]?


  • 3

    @compton_scatter said in Java Concise Postorder Traversal Solution:

    @vincexu It is postorder (we process left and right subtrees before processing the current one)

    Yeah but what it returns is preorder. So it looks like it's named after an implementation detail instead of named after what it's for. Rather unusual and confusing. Maybe something like "collect" would be a better name.


  • 0
    S

    Jesus, this is called preorder, isn't it?


  • 0
    S

    @StefanPochmann what's the complex of this solution, I'm not sure about it, it's 2^n, could you help me?


  • 0

    @pengshuang said in Java Concise Postorder Traversal Solution:

    The postOrder function can be simplified by

            if (map.getOrDefault(serial, 0) == 1) 
                res.add(cur);
            map.put(serial, map.getOrDefault(serial, 0) + 1);
    

    Just another way:

            if (Objects.equals(map.put(serial, map.getOrDefault(serial, 0) + 1), 1))
                res.add(cur);
    

    And yet another, using sets instead:

    public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
        List<TreeNode> res = new LinkedList<>();
        postorder(root, new HashSet<>(), new HashSet<>(), res);
        return res;
    }
    public String postorder(TreeNode cur, Set<String> first, Set<String> second, List<TreeNode> res) {
        if (cur == null) 
            return "#";  
        String serial = cur.val + "," + postorder(cur.left, first, second, res) + "," + postorder(cur.right, first, second, res);
        if (!first.add(serial) && second.add(serial))
            res.add(cur);
        return serial;
    }

  • 1

    @shuoshuo70 said in Java Concise Postorder Traversal Solution:

    @StefanPochmann what's the complex of this solution, I'm not sure about it, it's 2^n, could you help me?

    Why do you ask me? It's @compton_scatter's code and they're quite capable and responsive, no? And others might be able to tell as well.


  • 1
    Z

    @compton_scatter Hey, i'm confused, because i think only post order couldn't decide one tree. We need at least two orders to decide it? right?


  • 0

    @zmyzz Try to find a counter-example against this solution then.


  • 13
    S

    @zmyzz Because he added “#” to indicate no children of leaf nodes. By doing this, two different trees can never have same serial.

    However, without “#” to indicate null in leaf nodes, two different trees may have same pre-order or post-order serial.


Log in to reply
 

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