在函数定义中给出了二进制树的内存和级别排列遍历以及节点总数，我们必须计算给定输入的二进制树的最小高度。<<<<<<<<<<<<<<<<<<<<<<<<<<<</p>
我们可以在不构造树的情况下计算吗？
func(int[] inorder, int[] levelorder, int n)
{
// write code here
}
例如
- inorder traversal -
{ 4,2,5,1,6,3,7}， - LevelOrder Traversal -
{1,2,3,4,5,6,7}，n=7。
和预期的O/P是
3
代码段下面的代码段将计算树的高度而不构造树。
#include <iostream>
#include <queue>
using namespace std;
int minHeight(int inOrder[], int levelOrder[], int n)
{
int i=1;
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();
}
}
return height;
}
int main()
{
int inOrder[] = {4,2,5,1,6,3,7}; //input1
int levelOrder[] = {1,2,3,4,5,6,7}; //input2
int n=sizeof(inOrder)/sizeof(int); ////input3
cout<<minHeight(inOrder, levelOrder, n)<<endl;
return 0;
}
问题：如果给出了树的内和水平顺序遍历，则树的最小高度
是多少示例1：
input1 : {2,1,3}
input2 : {1,2,3}
input3 : 3
Output : 2
示例2：
input1 : {4,2,5,2,6,3,7}
input2 : {1,2,3,4,5,6,7}
input3 : 7
Output : 3
如果您在Naggaro的校园回合或Metti中得到了这个问题，那么它将为您提供一个很好的解决方案
class Node:
def __init__(self, key):
self.data = key
self.left = None
self.right = None
def buildTree(level, ino):
if ino:
for i in range(0, len(level)):
if level[i] in ino:
node = Node(level[i])
io_index = ino.index(level[i])
break
if not ino:
return node
node.left = buildTree(level, ino[0:io_index])
node.right = buildTree(level, ino[io_index + 1:len(ino)])
return node
def height(root):
if root is None:
return 0
else:
return max(height(root.left),height(root.right))+1
#This is the function you have to write
def minHeight(input1,input2,input3):
global root
root = buildTree(input1, input2)
return height(root)
inorder = [4,2,5,1,6,3,7]
levelorder = [1,2,3,4,5,6,7]
print("height : ",minHeight(levelorder,inorder,len(inorder)))
一种非常简单的方法是建造树，然后找到高度。
让我们假设节点的结构是： 结构节点 { int键; struct节点 *左， *右； };
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<<" ";**
}
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;
}
二进制树的最小可能高度为 log2(n+1)，其中n是节点的数量。