使用前序遍历的二叉树的最大宽度

Question

我想获得二叉树的最大宽度。在这种方法中，可以使用预序遍历宽度来计算。但我无法正确理解它。请解释函数 getMaxWidthRecur() 是如何工作的。

// A utility function that returns maximum value in arr[] of size n
    int getMax(int arr[], int n);

/* A function that fills count array with count of nodes at every
   level of given binary tree*/

    void getMaxWidthRecur(struct node *root, int count[], int level);

// Function to get the maximum width of a binary tree
    int getMaxWidth(struct node* root){
    int h = height(root);

    // Create an array that will store count of nodes at each level
    int *count = (int *)calloc(sizeof(int), h);
    int level = 0;

    // Fill the count array using preorder traversal
    getMaxWidthRecur(root, count, level);

    // Return the maximum value from count array
    return getMax(count, h);
}

// A function that fills count array with count of nodes at every
// level of given binary tree
void getMaxWidthRecur(struct node *root, int count[], int level){
    if(root){
         count[level]++;
         getMaxWidthRecur(root->left, count, level+1);
         getMaxWidthRecur(root->right, count, level+1);
    }
}

Answer 1

主要工作正在 getMaxWidthRecur 中完成。它最初被赋予参数 level = 0。每当我们向下递归树中的一个级别时，level 参数就会递增 1。递归将恰好命中树中的每个节点一次，并且对于树中的每个节点，它都会将 count[level] 递增 1。所以当它用尽树中的所有节点时，count[i] 将等于树在深度 i 处的宽度。

使用前序遍历的二叉树的最大宽度

Maximum width of a Binary Tree using preorder traversal

c++

tree

binary-tree

binary-search-tree

data-structures