东哥带你刷二叉树（后序篇） :: labuladong的算法小抄

[utterances-bot]

文章链接点这里：东哥带你刷二叉树（后序篇）

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

[Asber777]

打卡

[lovelyJason]

/**
 * @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测试没通过， 并且力扣里面执行代码和提交代码对测试用例的结果不同？执行代码是对的，提交时，同一用例说我输出错误

[HCWGH]

res的结果是有顺序要求的，这个是后续遍历。所以需要主要的是放置结果需要头插法才能保证结果是 自顶向下的

[leozhang007]

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

[clearlovel7]

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

[lovelyJason]

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

嗯是这个问题

[861130245]

可恶的合作方（bushi）

[ayccwhd]

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

[KevinZhou92]

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

 0               0
    \             /
     0         0

你可以试试这两个

[ayccwhd]

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

[Vivian-wh]

打卡打卡

[David-qiuwenhui]

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;
};

[leibnizl]

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

[lemonadeseason]

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

[fly-adser]

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

[KevinZhou92]

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

[cheng-miao]

daka

[LebronHarden1]

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

[SUN7700]

肯定不行啊，你这样是把每个出现过的子树返回了，题目要求是返回出现两次及以上的字数

[KelleyYin]

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

[rzw200]

在美国不能够用微信付款。有没有其它付款办法?

[LeeHaruYa]

滴滴滴打卡

[JunyuHuang98]

请问有朋友遇到这个test case怕不过的吗，我这显示175/176
输入： root =[10,2,22,1,12,1,1]
输出： [[1],[22,1,1]]
预期结果： [[1]]

[zhaowenhao1234]

拼接字符串的时候中间加个逗号吧，会出现这个情况：（##1，##12，2） 和 （##1，##1，22）两个不同的子树。去掉逗号的结果都是 ##1##122.。。。。

[yonggui-yan]

打卡
看完好心人评论的代码。感觉像是：
把每个node为根的子树作为 hashmap的key, 然后检查是否hashmap[key]为2.

然后“子树”用序列化的字符结果表示。key不能是树，也不能是list，但可以是字符串。

[SUN7700]

这个case过不去
输入：[0,0,0,0,null,null,0,null,null,null,0]

[reatiny]

java版

class Solution {
    HashMap<String, Integer> map = new HashMap<>(); 
    List<TreeNode> res = new ArrayList<>();
    public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
        dfs(root);
        return res;
    }

    public String dfs(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        if (root == null) return "#";
        String key = sb.append(root.val).append("-").append(dfs(root.left)).append(dfs(root.right)).toString();
        
        map.put(key, map.getOrDefault(key, 0) + 1);
        if(map.get(key) == 2) {
            res.add(root);
        }
        return key;
    }
    
}

[jxs1211]

go version:

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
// postorder is commonly used for resolve kinds of subtree problem
func findDuplicateSubtrees(root *TreeNode) []*TreeNode {
    res, set := []*TreeNode{}, map[string]int{}
    dfs(root, set, &res)
    return res
}

func dfs(root *TreeNode, set map[string]int, res *[]*TreeNode) string {
    if root == nil {return "#"}
    l := dfs(root.Left, set, res)
    r := dfs(root.Right, set, res)
    subTreeStr := l + "," + r + "," + strconv.Itoa(root.Val)
    set[subTreeStr]++
    // add to result when we only found the subTreeString appeared at the second time
    if count, _ := set[subTreeStr]; count == 2{          
      *res = append(*res, root)
    }
    return subTreeStr
}```

[huzhiqiang1998]

c++ version

    class Solution {
    public:

    unordered_map<string,int> hashmap;
    vector<TreeNode*>res;

    string traverse(TreeNode* root)
    {
        if(root==NULL)
        return "#";

        string left=traverse(root->left);
        string right=traverse(root->right);
        string subtree=left+","+right+","+to_string(root->val);
        
        if(hashmap[subtree]==1)
        res.push_back(root);
        hashmap[subtree]++;
        return subtree;
    }

    vector<TreeNode*> findDuplicateSubtrees(TreeNode* root) 
    {
        traverse(root);
        return res;
    }
    };

[SUN7700]

还有一个三元组方法，希望东哥可以更新进来~

[weixueman]

序列化没加逗号，map中会检测到重复的key，很奇怪。
最开始代码如下，测试不通过：
StringBuilder sb = new StringBuilder(root.val);
sb.append(find(root.left));
sb.append(find(root.right));
进行如下修改后就没问题了。
StringBuilder sb = new StringBuilder(root.val+",");
sb.append(find(root.left)).append(",");
sb.append(find(root.right)).append(",");

[labuladong]

"12" + "3" -> "123"
"1" + "23 -> "123"
如果不在中间放个特殊符号做分隔符，你能分清这两种的区别吗？

[xamddewey]

Go version

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

import "strconv"

func findDuplicateSubtrees(root *TreeNode) []*TreeNode {
    res := make([]*TreeNode, 0)
    nodeSeqMap := make(map[string]int)

    var serialize func(*TreeNode) string
    serialize = func(node *TreeNode) string {
        if node == nil {
            return "#"
        }
        seq := serialize(node.Left) + "," + serialize(node.Right) + "," + strconv.Itoa(node.Val)
        if nodeSeqMap[seq] == 1 {
            res = append(res, node)
        }
        nodeSeqMap[seq] += 1
        return seq
    }

    serialize(root)
    return res
}