LeetCode：寻找重复的子树_652

Yuyy

发布于 2022-06-28 20:39:17

22000

代码可运行

文章被收录于专栏：yuyy.info技术专栏yuyy.info技术专栏

运行总次数：0

代码可运行

思路

问题一：如果遍历比较

遍历所有节点，然后两两比较。时间复杂度O(n)。一看性能就不行。
利用set来判断是否重复。不过有重复多次的情况，但只需返回一个重复节点，所以还需要记录count，使用map即可。

问题二：如何判断两个节点结构相同

通过递归，同时遍历两个节点。因为一个节点需要和多次比较，所以同一个节点需要遍历多次，性能差。
序列化二叉树。将二叉树遍历，转成字符串。不过需要注意
1. 中序无法反序列化
2. 中序的序列化是不能确定二叉树的，前序和后序就行。具体原因还没想清楚，正在LeetCode请教大佬。

题目

给定一棵二叉树，返回所有重复的子树。对于同一类的重复子树，你只需要返回其中任意一棵的根结点即可。

两棵树重复是指它们具有相同的结构以及相同的结点值。

示例 1：

下面是两个重复的子树：

      2
     /
    4

和

因此，你需要以列表的形式返回上述重复子树的根结点。

代码

class Solution {
        private List<TreeNode> res = new ArrayList<>();
        private Map<String, Integer> memo = new HashMap<>();

        public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
            serializeNode(root);
            return res;
        }

        private String serializeNode(TreeNode root) {
            if (root == null) {
                return "#";
            }

            String left = serializeNode(root.left);
            String right = serializeNode(root.right);
            // 序列化二叉树
            String curr = left + "," + right + "," + root.val;

            Integer count = memo.getOrDefault(curr, 0);
            if (count == 1) {
                res.add(root);
            }
            memo.put(curr, count + 1);
            return curr;
        }
    }

Post Views: 158

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2021-10-29 ，如有侵权请联系 cloudcommunity@tencent.com 删除

二叉树