给定一棵二叉树的先序遍历序列和中序遍历序列,要求计算该二叉树的高度。 输入格式: 输入首先给出正整数N(≤50),为树中结点总数。下面两行先后给出先序和中序遍历序列,均是长度为N的不包含重复英文字母(区别大小写)的字符串。 输出格式: 输出为一个整数,即该二叉树的高度。 输入样例: 9 ABDFGHIEC FDHGIBEAC 输出样例: 5
时间: 2023-07-24 13:42:17 浏览: 157
这道题需要我们先根据先序遍历序列和中序遍历序列构建一棵二叉树,然后再计算该二叉树的高度。
构建二叉树的过程可以使用递归来实现。具体来说,我们可以根据先序遍历序列中的第一个结点来确定根结点,然后在中序遍历序列中找到该结点的位置,这样就可以将中序遍历序列划分为左右两个部分。然后我们可以递归地构建左子树和右子树。
在计算二叉树的高度时,我们可以分别计算左子树和右子树的高度,然后取其最大值加上 1 即可。
下面是 Python 代码实现:
```python
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def buildTree(preorder, inorder):
if not preorder:
return None
root = TreeNode(preorder[0])
i = inorder.index(preorder[0])
root.left = buildTree(preorder[1:i+1], inorder[:i])
root.right = buildTree(preorder[i+1:], inorder[i+1:])
return root
def getHeight(root):
if not root:
return 0
leftHeight = getHeight(root.left)
rightHeight = getHeight(root.right)
return max(leftHeight, rightHeight) + 1
n = int(input())
preorder = input()
inorder = input()
root = buildTree(preorder, inorder)
print(getHeight(root))
```
下面是 C++ 代码实现:
```cpp
#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;
struct TreeNode {
char val;
TreeNode* left;
TreeNode* right;
TreeNode(char v) : val(v), left(nullptr), right(nullptr) {}
};
TreeNode* buildTree(string& preorder, string& inorder, int preStart, int inStart, int inEnd, unordered_map<char, int>& pos) {
if (preStart >= preorder.size() || inStart > inEnd) {
return nullptr;
}
TreeNode* root = new TreeNode(preorder[preStart]);
int i = pos[root->val];
root->left = buildTree(preorder, inorder, preStart + 1, inStart, i - 1, pos);
root->right = buildTree(preorder, inorder, preStart + (i - inStart) + 1, i + 1, inEnd, pos);
return root;
}
int getHeight(TreeNode* root) {
if (!root) {
return 0;
}
int leftHeight = getHeight(root->left);
int rightHeight = getHeight(root->right);
return max(leftHeight, rightHeight) + 1;
}
int main() {
int n;
cin >> n;
string preorder, inorder;
cin >> preorder >> inorder;
unordered_map<char, int> pos;
for (int i = 0; i < inorder.size(); i++) {
pos[inorder[i]] = i;
}
TreeNode* root = buildTree(preorder, inorder, 0, 0, inorder.size() - 1, pos);
cout << getHeight(root) << endl;
return 0;
}
```
在 C++ 中,我们使用了哈希表 `pos` 来保存中序遍历序列中每个结点的位置,这样可以使查找某个结点的位置的时间复杂度降为 O(1)。同时,我们也将 `buildTree` 函数的参数更改为了传递下标,以避免递归时频繁地拷贝字符串。
阅读全文