Нахождение минимальной высоты бинарного дерева с заданным порядком следования по порядку и уровню

Question

Обходы порядка и уровня заказа для двоичного дерева вместе с общим числом узлов приведены в определении функции, мы должны вычислить минимальную высоту двоичного дерева для заданных входных данных.

Можем ли мы вычислитьбез построения дерева?

func(int[] inorder, int[] levelorder, int n)
{
  // write code here
}

например

• обход по порядку - { 4,2,5,1,6,3,7},
• обход по уровню - {1,2,3,4,5,6,7}, n=7.

А ожидаемое о / п было 3

Answer 1

yes, you can do that without even constructing the tree.
for that use two queue.
see given below code for better understanding.

void **buildTree**(int inorder[], int levelOrder[], int i, int j,int n)
{
    queue<int>q1,q2;
    q1.push(levelOrder[0]);
    int k = 1,height = 0;
    while(!q1.empty() || !q2.empty()){
        if(!q1.empty()) height++;
        while(!q1.empty()){
            int val = q1.front();
            for(int i = 0;i<n;++i){
                if(inorder[i] == val) break;
            }
            if(i>0 && inorder[i-1] !=-1 && k<n)
                q2.push(levelOrder[k++]);
            if(i<n-1 && inorder[i+1] !=-1 && k<n) 
                q2.push(levelOrder[k++]);
            inorder[i] = -1;
            q1.pop();
        }
        if(!q2.empty()) height++;
        while(!q2.empty()){
            int val = q2.front();
            for(int i = 0;i<n;++i){
                if(inorder[i] == val) break;
            }
            if(i>0 && inorder[i-1] !=-1 && k<n)  
                q1.push(levelOrder[k++]);
            if(i<n-1 && inorder[i+1] !=-1 && k<n) 
                q1.push(levelOrder[k++]);
            inorder[i] = -1;
            q2.pop();
        }
    }
 cout<<height<<endl;
}

Answer 2

Минимально возможная высота двоичного дерева равна log2(n+1), где n - количество узлов.

Answer 3

очень простой подход состоит в том, чтобы построить дерево и затем найти его высоту.

давайте предположим, что структура узла: struct Node {int key;struct Node * left, * right;};

Node* **newNode**(int key)
{
Node *node = (Node *)malloc(sizeof(Node));
node->key = key;
node->left = node->right = NULL;
return (node);
}
int **getHeight**(Node* root){
    if(root==NULL) return 0;
    return max(getHeight(root->left)+1,getHeight(root->right)+1);
}
Node* **getNode**(Node* root,int key){
    if(root!=NULL){
        if(root->key == key) return root;
        return getNode(root->left,key) != NULL ? getNode(root->left,key):
        getNode(root->right,key);
    }
}
void **buildTree**(int inorder[], int levelOrder[], int i, int j,int n)
{
  Node* head = newNode(levelOrder[0]);
  i++;
 int comp = 0;
 while(i<j){
      int key = levelOrder[comp];
      Node* ptr = getNode(head,key);
      int k = n-1;
      while(k>=0 && inorder[k]!=key) k--;
      if(k>0 && inorder[k-1]!=-1){
          ptr->left = newNode(levelOrder[i]);
          i++;
      }
      if(k<n-1 && inorder[k+1]!=-1){
          ptr->right = newNode(levelOrder[i]);
          i++;
      }
   inorder[k] = -1;
   comp++;
}
int height = getHeight(head);
  **cout<<height<<" ";**
}