LeetCode 652. 寻找重复的子树

题目

分析

首先，我们要知道一棵树长啥样，就需要遍历这棵树。我们需要知道某个节点下面的树长啥样，需要把该节点放到最后遍历，先遍历左孩子和右孩子。因此采用后序遍历。
其次，我们需要知道所有的其他子树长什么样，这样才能比较这棵子树和其他子树是否相同。因此我们在遍历的时候，将其序列化。然后存到HashMap中。

代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    LinkedList<TreeNode> nodeList = new LinkedList<TreeNode>();
    HashMap<String, Integer> map = new HashMap<String, Integer>();
    public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
        if (root == null) return null;
        traversal(root);
        return nodeList;
    }

    private String traversal(TreeNode root){
        if (root == null) return "#";
        String leftStr = traversal(root.left);
        String rigthStr = traversal(root.right);
        String str = leftStr + "," + rigthStr + "," + String.valueOf(root.val); 
        if (map.containsKey(str)){
            if (map.get(str) == 1){
                map.put(str, 2);
                nodeList.add(root);
            }
        }
        else{
            map.put(str, 1);
        }
        return str;
    }
}

性能优化后的代码（主要将String换成了StringBuilder），优化后的代码就不怎么直观了。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    LinkedList<TreeNode> nodeList = new LinkedList<TreeNode>();
    HashMap<String, Integer> map = new HashMap<String, Integer>();
    public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
        traversal(root);
        return nodeList;
    }

    private String traversal(TreeNode root){
        if (root == null) return "#";
        StringBuilder leftStr = new StringBuilder(traversal(root.left));
        String subStr = leftStr.append(",").append(traversal(root.right)).append(",").append(String.valueOf(root.val)).toString();
        int times = map.getOrDefault(subStr, 0);
        if (times == 1){
            nodeList.add(root);
        }
        map.put(subStr, times + 1);
        return subStr;
    }
}