找到二叉树的宽度

Question

找到二叉树的宽度。

在我的每个假期的代码中，我在哈希映射中创建一个条目，并在我离开i时找到一个节点时不断更新它。最后我将迭代hashmap以找到最大宽度。但是我怎么能不使用任何classleel / global varaiables？

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

Answer 2

您无需跟踪每个级别的节点数。

将每个节点的水平位置定义为右子节点数减去从根节点到节点的左子节点数。然后宽度将是最大水平位置减去最小水平位置。最小/最大位置可以在两个组件的数组中围绕递归遍历传递。

这是我的意思的代码示例：

int getWidth(Node node) {
    // current[0] is the number of left children traversed of the current path
    // current[1] is the number of right children traversed of the current path
    int[] current = { 0, 0 };
    // extremes[0] is the minimum horizontal position
    // extremes[1] is the maximum horizontal position
    int[] extremes = { 0, 0 };
    computeExtremes(node, current, extremes);
    return (extremes[1] - extremes[0]);
}

void computeExtremes(Node node, int[] current, int[] extremes) {
    if (node == null) { return; }
    int position = current[1] - current[0];
    if (extremes[0] > position) {
        extremes[0] = position;
    }
    if (extremes[1] < position) {
        extremes[1] = position;
    }
    current[0]++;
    computeExtremes(node.left, current, extremes);
    current[0]--;
    current[1]++;
    computeExtremes(node.right, current, extremes);
    current[1]--;
}

Answer 3

如果我理解正确你想做这样的事情？

public Map<Integer,Integer> width( Node node ) {
    Map<Integer,Integer> mp = new HashMap<Integer,Integer>();
    width( node, 1, mp );
    return mp;
}

private void width( Node node, int level, Map<Integer,Integer> mp ) {
    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 4

这使用了@ nathan的算法，但是通过了价值。

Pair<int, int> extremes(Node node, int x, int y) {
  if (node == null) return makePair(x,y);
  Pair p1 = extremes(node.left, x-1, y);
  Pair p2 = extremes(node.right, x, y+1);
  return makePair(min(p1.x, p2.x), max(p1.y, p2.y))
}

Answer 5

见https://www.geeksforgeeks.org/maximum-width-of-a-binary-tree/

对哈希表使用递归

int getWidth(struct node* root, int level)
{

  if(root == NULL)
    return 0;

  if(level == 1)
    return 1;

  else if (level > 1)
    return getWidth(root->left, level-1) + 
             getWidth(root->right, level-1);
}

使用队列将父队列出列并替换为子节点

static int maxwidth(node root) 
    {
        // Base case
        if (root == null)
            return 0;

        // Initialize result
        int maxwidth = 0;

        // Do Level order traversal keeping 
        // track of number of nodes at every level
        Queue<node> q = new LinkedList<>();
        q.add(root);
        while (!q.isEmpty()) 
        {
            // Get the size of queue when the level order
            // traversal for one level finishes
            int count = q.size();

            // Update the maximum node count value
            maxwidth = Math.max(maxwidth, count);

            // Iterate for all the nodes in 
            // the queue currently
            while (count-- > 0) 
            {
                // Dequeue an node from queue
                node temp = q.remove();

                // Enqueue left and right children 
                // of dequeued node
                if (temp.left != null) 
                {
                    q.add(temp.left);
                }
                if (temp.right != null) 
                {
                    q.add(temp.right);
                }
            }
        }
        return maxwidth;
    }

Answer 6

有点不同的东西：

int[] width(Node node){
    if(node==null) {
        return new int[]{};
    }
    int[] la = width(node.left);
    int[] ra = width(node.right);
    return merge(1, la, ra);
}


private int[] merge(int n0, int[] la, int[] ra) {
    int maxLen = Math.max(la.length, ra.length);
    int[] result = new int[maxLen+1];
    result[0] = n0;
    for (int i = 0; i < maxLen; ++i) {
        result[i+1] = i >= la.length
                ? ra[i] : i >= ra.length
                ? la[i] : la[i] + ra[i];
    }
    return result;
}