java - 找到二叉树的宽度

Question

求二叉树的宽度。

在每次休假的代码中，我在 HashMap 中创建一个条目，并在我在休假 i 处找到一个节点时不断更新它。最后我将迭代 HashMap 以找到最大宽度。但是我如何在不使用任何节点的情况下做到这一点类/全局变量？

Map<Integer,Integer> mp = new HashMap<Integer,Integer>();
void width(Node node,int level){
        if(node==null)
            return;
        if(mp.containsKey(level)){
            int count = mp.get(level);
            mp.put(level, count+1);
        }else{
            mp.put(level, 1);
        }

        width(node.left, level+1);
        width(node.right, level+1);

    }

Answer 1

只需在方法内部创建 HashMap，然后将所有工作移至辅助方法中，如下所示:

void width(Node node,int level){
    Map<Integer,Integer> mp = new HashMap<Integer,Integer>();
    widthImpl(mp, node, level);
    // find maximum
}

private void widthImpl(Map<Integer,Integer> mp, Node node, int level) {
    if(node==null)
        return;
    if(mp.containsKey(level)){
        int count = mp.get(level);
        mp.put(level, count+1);
    }else{
        mp.put(level, 1);
    }

    widthImpl(mp, node.left, level+1);
    widthImpl(mp, node.right, level+1);
}