найти ширину бинарного дерева

Question

Нахождение ширины бинарного дерева.

В своем коде для каждого отпуска я создаю запись в хэш-карте и продолжаю обновлять ее, когда я нашел узел в отпуске.найти максимальную ширину. Но как я могу это сделать без использования каких-либо классов / глобальных переменных?

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

Что-то немного другое:

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

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

Используется алгоритм @ 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))
}