LeetCode:寻找重复的子树_652

思路

问题一:如果遍历比较

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

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

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

题目

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

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

示例 1:

        1
       / \
      2   3
     /   / \
    4   2   4
       /
      4

下面是两个重复的子树:

      2
     /
    4

    4

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

Related Topics
  • 深度优先搜索
  • 广度优先搜索
  • 二叉树
  • 👍 324
  • 👎 0
  • 代码

    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;
            }
        }
    作者:Yuyy
    博客:https://yuyy.info
    暂无评论

    发送评论 编辑评论

    
    				
    |´・ω・)ノ
    ヾ(≧∇≦*)ゝ
    (☆ω☆)
    (╯‵□′)╯︵┴─┴
     ̄﹃ ̄
    (/ω\)
    ∠( ᐛ 」∠)_
    (๑•̀ㅁ•́ฅ)
    →_→
    ୧(๑•̀⌄•́๑)૭
    ٩(ˊᗜˋ*)و
    (ノ°ο°)ノ
    (´இ皿இ`)
    ⌇●﹏●⌇
    (ฅ´ω`ฅ)
    (╯°A°)╯︵○○○
    φ( ̄∇ ̄o)
    ヾ(´・ ・`。)ノ"
    ( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
    (ó﹏ò。)
    Σ(っ °Д °;)っ
    ( ,,´・ω・)ノ"(´っω・`。)
    ╮(╯▽╰)╭
    o(*////▽////*)q
    >﹏<
    ( ๑´•ω•) "(ㆆᴗㆆ)
    😂
    😀
    😅
    😊
    🙂
    🙃
    😌
    😍
    😘
    😜
    😝
    😏
    😒
    🙄
    😳
    😡
    😔
    😫
    😱
    😭
    💩
    👻
    🙌
    🖕
    👍
    👫
    👬
    👭
    🌚
    🌝
    🙈
    💊
    😶
    🙏
    🍦
    🍉
    😣
    Source: github.com/k4yt3x/flowerhd
    颜文字
    Emoji
    小恐龙
    花!
    上一篇
    下一篇