fucking-algorithm 东哥带你刷二叉树（后序篇）

评论礼仪见这里，违者直接拉黑。

May 23 '21 09:05 utterances-bot

东哥，我们这个代码复杂度是O(n^2)，然后LeetCode的讨论区老哥用了个O(n)的方法，但我没太看懂他为啥能降到O(n)，跟我们解法的区别在哪，东哥可以看一下吗

Class Solution {
    int curId = 1;
    Map<String, Integer> serialToId = new HashMap<>();
    Map<Integer, Integer> idToCount = new HashMap<>();
    List<TreeNode> res = new LinkedList<>();
    
    public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
        postorder(root);
        return res;
    }
    
    private int postorder(TreeNode root) {
        if (root == null) {
            return 0;
        }
        
        int leftId = postorder(root.left);
        int rightId = postorder(root.right);
        String curSerial = leftId + "," + root.val + "," + rightId;
        int serialId = serialToId.getOrDefault(curSerial, curId);
        
        if (serialId == curId) {
            curId++;
        }
    
        serialToId.put(curSerial, serialId);
        idToCount.put(serialId, idToCount.getOrDefault(serialId, 0) + 1);
        
        if (idToCount.get(serialId) == 2) {
            res.add(root);
        } 
        return serialId;
    }
    
}

Jan 04 '22 04:01 MessiahChen

打卡

Jan 19 '22 05:01 Asber777

/**
 * @param {TreeNode} root
 * @return {TreeNode[]}
 */
let memo = new Map()
let res = []

function findDuplicateSubtrees(root) {
  traverse(root)
  return res
} 
function traverse(root) {
    if(root == null) {
        return '#'
    }
    let leftValue = traverse(root.left)
    let rightValue = traverse(root.right)
    let subTree = leftValue + ',' + rightValue + ',' + root.val
    let freq = memo.get(subTree) || 0
    if(freq == 1) {
        res.push(root)
    }
    memo.set(subTree, freq + 1)
    return subTree
}

这个好奇怪，同东东的java代码逻辑一模一样， leetcode测试没通过，并且力扣里面执行代码和提交代码对测试用例的结果不同？执行代码是对的，提交时，同一用例说我输出错误

Jan 28 '22 06:01 lovelyJason

@lovelyJason memo 和 res 变量在全局有上次单测的结果，所以报错了，把这两个变量放到函数内定义试试

Feb 23 '22 14:02 leozhang007

python 版

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def __init__(self):
        self.res=[]
        self.hashmap={}

    def traverse(self,root):
        if root==None:
            return '#'
        left=self.traverse(root.left)
        right=self.traverse(root.right)

        subtree=left+","+right+","+str(root.val)
        fre=self.hashmap.get(subtree,0)
        if fre==1:
            self.res.append(root)
        self.hashmap[subtree]=fre+1
        return subtree
    
    def findDuplicateSubtrees(self, root: Optional[TreeNode]) -> List[Optional[TreeNode]]:
        self.traverse(root)
        return self.res

Mar 07 '22 07:03 clearlovel7

@lovelyJason memo 和 res 变量在全局有上次单测的结果，所以报错了，把这两个变量放到函数内定义试试

嗯是这个问题

Mar 07 '22 07:03 lovelyJason

可恶的合作方（bushi）

Mar 22 '22 12:03 861130245

为什么left + "," + root.val + "," + right ; 有一个用例会错误。。感觉思路是一样的啊

Apr 01 '22 10:04 ayccwhd

@ayccwhd 因为中序遍历的话, 左节点为None, 和右节点为None, 序列化出来是同一个string

 0               0
    \             /
     0         0

你可以试试这两个

Apr 01 '22 18:04 KevinZhou92

@KevinZhou92 感谢，这里困惑了好久

Apr 02 '22 03:04 ayccwhd

打卡打卡

Apr 04 '22 01:04 Vivian-wh

javascript version

var findDuplicateSubtrees = function(root) {
    // 记录所有子树以及出现的次数
    let mapSet = new Map();
    // 记录重复的子树根节点
    let res = [];

    function traverse(node) {
        // base case 空节点使用特殊的字符表示
        if (!node) {
            return "#";
        }
        
        let leftNode = traverse(node.left);
        let rightNode = traverse(node.right);

        /****** 后序位置 ******/
        // 将左右子树和node节点序列化成字符串
        let nodeString = leftNode + "," + rightNode + "," + node.val;
        
        // 让每个节点把自己的序列化结果存进去 查询得到有没有其他节点的子树与自己重复
        let freq = mapSet.get(nodeString) || 0;
        // 多次重复也只会被加入结果集一次
        if (freq == 1){
            res.push(node);
        }
        // 给子树对应的出现次数加一
        mapSet.set(nodeString, freq + 1);
        /*********************/

        return nodeString;
    }

    traverse(root);
    return res;
};

Apr 15 '22 01:04 David-qiuwenhui

有意思，这题又正好能用上前文序列化篇的内容，没去公众号看解法，但是感觉使用序列化一下子树，然后放到map里面存一下貌似就行了

Apr 27 '22 15:04 leibnizl

python代码：

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
import collections
NULL = "201"
class Solution:
    def findDuplicateSubtrees(self, root: Optional[TreeNode]) -> List[Optional[TreeNode]]:
        subtree_dict = collections.defaultdict(int)
        self.ans = []
        def traverse(root):
            if not root:
                return NULL
            left_preorder = traverse(root.left)
            right_preorder =  traverse(root.right)
            preorder = str(root.val) + " " +left_preorder + " " + right_preorder
            subtree_dict[preorder] += 1
            if subtree_dict[preorder] == 2:
                self.ans.append(root)
            return preorder
        traverse(root)
        return self.ans

May 10 '22 08:05 lemonadeseason

@KevinZhou92 这两个中序遍历一个是：0,0，null，一个是null，0,0，不一样啊

May 21 '22 16:05 fly-adser

@fly-adser 不是, 两个都是 #,0,#,0,#

May 21 '22 17:05 KevinZhou92

daka

May 25 '22 07:05 cheng-miao

东哥,这题能不能把每个节点的序列化结果都人丢进hashset里头,最后都拿出来存到list中进行返回?

May 31 '22 12:05 LebronHarden1

from collections import defaultdict
class Solution:
    def findDuplicateSubtrees(self, root: Optional[TreeNode]) -> List[Optional[TreeNode]]:
        if not root:
            return root
        hashmap = defaultdict(lambda: 0)
        res     = []
        def traverse(root):
            if not root:
                return "#"
            left_nodes  = traverse(root.left)
            right_nodes = traverse(root.right)
            res_str = left_nodes + ',' + right_nodes + ',' + str(root.val)
            if res_str in hashmap and hashmap[res_str] == 1:
                res.append(root)
            hashmap[res_str] += 1
            return res_str
        traverse(root)
        return res