时间戳

首页 > 解决方案 > 将二叉树中的重复节点映射到哈希图

java - 将二叉树中的重复节点映射到哈希图

问题描述

我正在尝试创建一个函数，该函数在二叉树中搜索以查找重复节点，并将每个唯一节点在树中出现的次数存储到哈希图中。

这是问题的更具体版本-

“创建一个名为 YourBinaryTree 的公共类，它扩展了 BinaryTree。覆盖受保护的 Map<Object, Integer> valueCount() 并让它返回一个 Map，将树中的每个对象映射到它出现的次数。如果树为空（根为空）你应该返回一个空地图。不要在你的类中声明任何字段“

我尝试递归搜索树，但我似乎无法让它工作，因为重复节点正在创建新映射而不是替换旧映射的值。

这是我到目前为止编写的代码：

import java.util.Map;
import java.util.HashMap;

public class YourBinaryTree extends BinaryTree
{

protected Map<Object, Integer> valueCount()
{
    Map<Object, Integer> treeMap = new HashMap<>();
    
    if(root == null)
    {
        return treeMap;
    }
    
    if(root.left == null && root.right == null)
    {
        treeMap.put(root.value , 1);
        return treeMap;
    }
    
    return valueCount(root);
}

private Map<Object, Integer> valueCount(Node current)
{
    Map<Object, Integer> treeMap = new HashMap<>();
    
    if(current == null)
    {
        return treeMap;
    }
    
    if(treeMap.containsKey(current.value))
    {
        treeMap.put(current.value, treeMap.get(current) + 1);
    }
    else
    {
        treeMap.put(current.value, 1);
    }
    /*
    Map<Object, Integer> treeMapLeft = new HashMap<>();
    Map<Object, Integer> treeMapRight = new HashMap<>();
    
    treeMapLeft.putAll(valueCount(current.left));
    treeMapRight.putAll(valueCount(current.right));
    
    treeMapRight.forEach(
            (key, value)
            -> treeMapLeft.merge(key, value, (v1, v2) -> v1+v2));
        
    
    treeMap = treeMapLeft;
    */
    treeMap.putAll(valueCount(current.left));
    treeMap.putAll(valueCount(current.right));
    
    return treeMap;
}

}

这是创建二叉树的类的代码：

public class BinaryTree
{
    protected class Node
    {
        protected Object value;
        protected Node left;
        protected Node right;
    
        Node(Object setValue)
        {
            value = setValue;
        }
    }
    protected Node root;
}

我试过使用合并功能，但我真的很确定如何实现它。任何帮助将不胜感激，谢谢！:)

标签： javahashmapbinary-tree

解决方案

我们只需要做一个简单的递归树遍历：

import java.util.Map;
import java.util.HashMap;

public class YourBinaryTree extends BinaryTree {
    private void traverse_tree(Node root, Map<Object, Integer> objectCountMap) {
        if(root == null) {
            return;
        }
        objectCountMap.putIfAbsent(root, 0);
        objectCountMap.put(root, objectCountMap.get(root) + 1);
        traverse_tree(root.left, objectCountMap);
        traverse_tree(root.right, objectCountMap);
    }

    public Map<Object, Integer> valueCount()
    {
        Map<Object, Integer> objectCountMap = new HashMap<>();
        traverse_tree(root, objectCountMap);
        return objectCountMap;
    }
}

注意关键的类应该正确objectCountMap实现equals()和hashcode()方法。

根据equals()和hashcode()类Object，只有当它们的内存地址相等时，两个对象才相等。
例如：

Object obj1 = new Object();
Object obj2 = new Object();
Map<Object, Integer> countMap = new HashMap<>();
countMap.put(obj1, 1);
countMap.put(obj2, 2);
countMap.get(obj1); // Returns 1
countMap.get(obj2); // Returns 2 

-----------

Object obj1 = new Object();
Object obj2 = obj1 // obj2 has same memory address as obj1
Map<Object, Integer> countMap = new HashMap<>();
countMap.put(obj1, 1);
countMap.put(obj2, 2);
countMap.get(obj1); // Returns 2
countMap.get(obj2); // Returns 2

推荐阅读