将重复节点从二叉树映射到哈希映射

Question

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

这是一个更具体的问题-

“创建一个名为YourBinaryTree的公共类，该类扩展BinaryTree。重写受保护的映射。”

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

以下是我迄今为止编写的代码：

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

我尝试过使用merge函数，但我真的很确定如何实现它。任何帮助都将不胜感激，谢谢！：）

Answer 1

如果要在valueCount方法中创建一个新映射，该映射为空，则需要在每次调用valueCount方法时传递在重写方法中创建的映射对象以进行更新。所以你的方法是这样的：

private void valueCount(Node current,HashMap<Object,Integer> treeMap){
     //rest of your code
}

Answer 2

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

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

注意ectivtCountMap的key的类应该正确实现equals（）和hashcode（）方法。

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

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