题目链接
代码随想录算法讲解
#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;
}
}
//方法三：借助类变量，无须真实构造二叉树
import java.util.*;
public class Main{
//类变量，用于记录递归过程中树的的最大高度
private static int res;
public static void main (String[] args) {
Scanner sc = new Scanner(System.in);
while(sc.hasNextLine()){
//将res清零
res = 0;
//读取输入数据
int n = Integer.parseInt(sc.nextLine());
String preOrder = sc.nextLine();
String inOrder = sc.nextLine();
//调用 constrcut 方法，获取二叉树的最大高度并保存在 res 变量中
Main.construct(preOrder,0,n - 1,
inOrder,0,n - 1,
1);
System.out.println(res);
}
sc.close();
return;
}
/**constrcut 函数：类似于根据先序遍历和中序遍历建立二叉树，但是
* 因为题目只要求获取树的最大高度，所以可以不真正建立二叉树
* 只要在每次遍历中多传一个 参数 height 表示当前所在树的高度
* 注意点 1: 区间表示法为 左闭右闭，即[start,end]
*/
private static void construct(String preOrder,int preStart,int preEnd,
String inOrder,int inStart,int inEnd,
int height){
//不合法的区间表示，说明已经达到叶子节点，不用往下接着构建
if(preStart > preEnd){
return;
}
// res 是表示的二叉树的最大高度，每次都判断取最大值
res = Math.max(res,height);
//根节点的值
char root = preOrder.charAt(preStart);
//index ：根节点在中序遍历的字符串的下标
int index = inStart;
while(index < inOrder.length() && inOrder.charAt(index) != root){
index+=1;
}
//左子树序列串的长度 = index - inStart
//所以左子树在现序遍历序列中的区间右端点(包含)为： index - inStart + preStart
int x = index - inStart + preStart;
//递归往下探索左子树，注意高度 + 1
construct(preOrder,preStart + 1,x,
inOrder,inStart,index - 1,
height + 1);
//递归往下探索右子树，注意高度 + 1
construct(preOrder,x + 1,preEnd,
inOrder,index + 1,inEnd,
height + 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()package main
import "fmt"
// 定义二叉树结构体
type treeNode struct {
val byte // 节点的值
left *treeNode // 左子树
right *treeNode // 右子树
}
// 先序遍历和中序遍历构建二叉树
func buildTree(preorder, inorder []byte) *treeNode {
if len(preorder) == 0 {
return nil
}
// 先序遍历的第一个节点是根节点
root := &treeNode{
val: preorder[0],
}
// 找到根节点在中序遍历序列中的位置
i := 0
for ; i < len(inorder); i++ {
if inorder[i] == root.val {
break
}
}
// 递归构建左右子树
root.left = buildTree(preorder[1:1+i], inorder[:i])
root.right = buildTree(preorder[1+i:], inorder[i+1:])
return root
}
// 计算二叉树的高度（深度）
func height(root *treeNode) int {
if root == nil {
return 0
}
leftHeight := height(root.left)
rightHeight := height(root.right)
if leftHeight > rightHeight {
return leftHeight + 1
} else {
return rightHeight + 1
}
}
func main() {
var k int
for {
_, err := fmt.Scan(&k)
if err != nil {
break
}
preorder := make([]byte, k)
inorder := make([]byte, k)
fmt.Scan(&preorder, &inorder)
// 构建二叉树
root := buildTree(preorder, inorder)
// 计算二叉树高度
fmt.Println(height(root))
}
}const rl=require("readline").createInterface({input:process.stdin});
const iter=rl[Symbol.asyncIterator]();
const readline=async ()=>(await iter.next()).value;
const out=process.stdout;
class Node{
constructor(data){
this.data=data;
this.left=null;
this.right=null;
}
getHeight(){
let leftHeight=0,rightHeight=0;
if(this.left!=null) leftHeight=this.left.getHeight();
if(this.right!=null) rightHeight=this.right.getHeight();
return Math.max(leftHeight,rightHeight)+1;
}
static createTree(preOrder,inOrder,preLeft,preRight,inLeft,inRight){
if(preLeft>preRight||inLeft>inRight) return null;
let rootIndex=inOrder.indexOf(preOrder[preLeft]);
let root=new Node(preOrder[preLeft]);
let leftNum=rootIndex-inLeft;
root.left=Node.createTree(preOrder,inOrder,preLeft+1,preLeft+leftNum,inLeft,rootIndex-1);
root.right=Node.createTree(preOrder,inOrder,preLeft+1+leftNum,preRight,rootIndex+1,inRight);
return root;
}
}
async function main(){
while(line=await readline()){
n=parseInt(line);
let preOrder=await readline();
let inOrder=await readline();
let root=Node.createTree(preOrder,inOrder,0,n-1,0,n-1);
console.log(root.getHeight());
}
}
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;
}