题目链接
代码随想录算法讲解
#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;
struct TreeNode {
char val;
TreeNode* left;
TreeNode* right;
TreeNode(char val) : val(val), left(nullptr), right(nullptr) {}
};
// 根据先序遍历和中序遍历序列构造二叉树
TreeNode* buildTree(string& preorder, string& inorder,
int preStart, int inStart, int inEnd,
unordered_map<char, int>& indexMap) {
if (preStart > preorder.size() - 1 || inStart > inEnd) {
return nullptr;
}
char rootValue = preorder[preStart];
TreeNode* root = new TreeNode(rootValue);
int rootIndex = indexMap[rootValue];
root->left = buildTree(preorder, inorder, preStart + 1, inStart, rootIndex - 1, indexMap);
root->right = buildTree(preorder, inorder, preStart + rootIndex - inStart + 1, rootIndex + 1, inEnd, indexMap);
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() {
int n;
while (cin >> n) {
string preorder, inorder;
cin >> preorder >> inorder;
unordered_map<char, int> indexMap;
for (int i = 0; i < n; ++i) {
indexMap[inorder[i]] = i;
}
TreeNode* root = buildTree(preorder, inorder, 0, 0, n - 1, indexMap);
int height = getHeight(root);
cout << height << endl;
}
return 0;
}
// 方法一：递归
import java.util.Scanner;
public class Main {
static class TreeNode {
char val;
TreeNode left;
TreeNode right;
TreeNode(char val) {
this.val = val;
this.left = null;
this.right = null;
}
}
private static TreeNode buildTree(String preOrder, String inOrder) {
if (preOrder.isEmpty())
return null;
char rootVal = preOrder.charAt(0);
TreeNode root = new TreeNode(rootVal);
int rootIdx = inOrder.indexOf(rootVal);
String leftPreOrder = preOrder.substring(1, rootIdx + 1);
String leftInOrder = inOrder.substring(0, rootIdx);
root.left = buildTree(leftPreOrder, leftInOrder);
String rightPreOrder = preOrder.substring(rootIdx + 1);
String rightInOrder = inOrder.substring(rootIdx + 1);
root.right = buildTree(rightPreOrder, rightInOrder);
return root;
}
private static int getHeight(TreeNode root) {
if (root == null)
return 0;
int leftHeight = getHeight(root.left);
int rightHeight = getHeight(root.right);
return Math.max(leftHeight, rightHeight) + 1;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (sc.hasNext()) {
sc.nextInt();
String preOrder = sc.next();
String inOrder = sc.next();
TreeNode root = buildTree(preOrder, inOrder);
int height = getHeight(root);
System.out.println(height);
}
sc.close();
}
}// 方法二：递归（使用哈希表来优化中序遍历中查找根节点位置的过程）
import java.util.HashMap;
import java.util.Scanner;
public class Main {
static class TreeNode {
char val;
TreeNode left;
TreeNode right;
TreeNode(char val) {
this.val = val;
this.left = null;
this.right = null;
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (sc.hasNext()) {
int N = sc.nextInt();
String preOrder = sc.next();
String inOrder = sc.next();
HashMap<Character, Integer> inOrderMap = new HashMap<>();
for (int i = 0; i < N; i++) {
inOrderMap.put(inOrder.charAt(i), i);
}
TreeNode root = buildTree(preOrder, 0, N - 1, 0, N - 1, inOrderMap);
int height = getHeight(root);
System.out.println(height);
}
sc.close();
}
private static TreeNode buildTree(String preOrder, int preStart, int preEnd, int inStart, int inEnd,
HashMap<Character, Integer> inOrderMap) {
if (preStart > preEnd || inStart > inEnd) {
return null;
}
char rootVal = preOrder.charAt(preStart);
TreeNode root = new TreeNode(rootVal);
int rootIndex = inOrderMap.get(rootVal);
int leftSubtreeSize = rootIndex - inStart;
root.left = buildTree(preOrder, preStart + 1, preStart + leftSubtreeSize, inStart, rootIndex - 1, inOrderMap);
root.right = buildTree(preOrder, preStart + leftSubtreeSize + 1, preEnd, rootIndex + 1, inEnd, inOrderMap);
return root;
}
private static int getHeight(TreeNode root) {
if (root == null) {
return 0;
}
int leftHeight = getHeight(root.left);
int rightHeight = getHeight(root.right);
return Math.max(leftHeight, rightHeight) + 1;
}
}class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def build_tree(pre_order, pre_start, pre_end, in_start, in_end, in_order_map):
if pre_start > pre_end or in_start > in_end:
return None
root_val = pre_order[pre_start]
root = TreeNode(root_val)
root_index = in_order_map[root_val]
left_subtree_size = root_index - in_start
root.left = build_tree(pre_order, pre_start + 1, pre_start + left_subtree_size, in_start, root_index - 1, in_order_map)
root.right = build_tree(pre_order, pre_start + left_subtree_size + 1, pre_end, root_index + 1, in_end, in_order_map)
return root
def get_height(root):
if not root:
return 0
left_height = get_height(root.left)
right_height = get_height(root.right)
return max(left_height, right_height) + 1
def main():
while True:
try:
N = int(input())
pre_order = input().strip()
in_order = input().strip()
in_order_map = {}
for i in range(N):
in_order_map[in_order[i]] = i
root = build_tree(pre_order, 0, N - 1, 0, N - 1, in_order_map)
height = get_height(root)
print(height)
except EOFError:
break
if __name__ == "__main__":
main()#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct TreeNode {
char val;
struct TreeNode* left;
struct TreeNode* right;
} TreeNode;
// 根据先序遍历和中序遍历序列构造二叉树
TreeNode* buildTree(char* preorder, char* inorder, int preStart, int inStart, int inEnd, int* indexMap) {
if (preStart > strlen(preorder) - 1 || inStart > inEnd) {
return NULL;
}
char rootValue = preorder[preStart];
TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
root->val = rootValue;
int rootIndex = indexMap[rootValue - 'a'];
root->left = buildTree(preorder, inorder, preStart + 1, inStart, rootIndex - 1, indexMap);
root->right = buildTree(preorder, inorder, preStart + rootIndex - inStart + 1, rootIndex + 1, inEnd, indexMap);
return root;
}
// 计算二叉树的高度
int getHeight(TreeNode* root) {
if (root == NULL) {
return 0;
}
int leftHeight = getHeight(root->left);
int rightHeight = getHeight(root->right);
return (leftHeight > rightHeight ? leftHeight : rightHeight) + 1;
}
int main() {
int n;
while (scanf("%d", &n) == 1) {
char preorder[100];
char inorder[100];
scanf("%s %s", preorder, inorder);
int* indexMap = (int*)malloc(26 * sizeof(int));
for (int i = 0; i < n; ++i) {
indexMap[inorder[i] - 'a'] = i;
}
TreeNode* root = buildTree(preorder, inorder, 0, 0, n - 1, indexMap);
int height = getHeight(root);
printf("%d\n", height);
free(indexMap);
indexMap = NULL;
free(root);
root = NULL;
}
return 0;
}