给定一棵二叉树的先序遍历序列和中序遍历序列,要求计算该二叉树的高度。
时间: 2023-04-23 08:00:32 浏览: 164
根据二叉树的先序遍历序列和中序遍历序列构建出二叉树之后,可以使用递归的方式计算该二叉树的高度。高度定义为根节点到最远叶子节点的距离。
每次递归计算左右子树的高度,取最大值+1作为当前节点的高度,最终返回根节点的高度即可。
相关问题
给定一棵二叉树的先序遍历序列和中序遍历序列,要求计算该二叉树的高度。并生成c++代码
以下是基于递归的 c++ 代码实现:
```c++
#include <iostream>
#include <vector>
using namespace std;
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
// 根据前序遍历和中序遍历构建二叉树
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder, int preStart, int inStart, int inEnd) {
if (preStart > preorder.size() - 1 || inStart > inEnd) {
return nullptr;
}
TreeNode* root = new TreeNode(preorder[preStart]);
int inIndex = 0;
for (int i = inStart; i <= inEnd; i++) {
if (inorder[i] == root->val) {
inIndex = i;
break;
}
}
root->left = buildTree(preorder, inorder, preStart + 1, inStart, inIndex - 1);
root->right = buildTree(preorder, inorder, preStart + inIndex - inStart + 1, inIndex + 1, inEnd);
return root;
}
// 计算二叉树高度
int getHeight(TreeNode* root) {
if (root == nullptr) {
return 0;
}
int leftHeight = getHeight(root->left);
int rightHeight = getHeight(root->right);
return max(leftHeight, rightHeight) + 1;
}
int main() {
vector<int> preorder{1, 2, 4, 5, 3, 6};
vector<int> inorder{4, 2, 5, 1, 3, 6};
TreeNode* root = buildTree(preorder, inorder, 0, 0, inorder.size() - 1);
cout << "The height of the binary tree is: " << getHeight(root) << endl;
return 0;
}
```
其中,`buildTree` 函数用于根据前序遍历和中序遍历构建二叉树,`getHeight` 函数用于计算二叉树高度。在 `main` 函数中,首先构建二叉树,然后调用 `getHeight` 函数计算二叉树的高度,并输出结果。
给定一棵二叉树的先序遍历序列和中序遍历序列,要求计算该二叉树的高度。并生成代码
以下是给定先序遍历序列和中序遍历序列计算二叉树高度的代码实现。
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def buildTree(preorder, inorder):
if not inorder:
return None
root_val = preorder.pop(0)
root = TreeNode(root_val)
index = inorder.index(root_val)
root.left = buildTree(preorder, inorder[:index])
root.right = buildTree(preorder, inorder[index+1:])
return root
def getHeight(root):
if not root:
return 0
left_height = getHeight(root.left)
right_height = getHeight(root.right)
return max(left_height, right_height) + 1
preorder = [3, 9, 20, 15, 7]
inorder = [9, 3, 15, 20, 7]
root = buildTree(preorder, inorder)
print(getHeight(root))
```
输出结果为:
```
3
```
说明该二叉树的高度为 3。
阅读全文