题目链接
代码随想录算法讲解
#include <iostream>
#include <unordered_map>
#include <string>
using namespace std;
// 定义二叉树节点结构
struct TreeNode {
char val;
TreeNode* left;
TreeNode* right;
TreeNode(int val) : val(val), left(nullptr), right(nullptr) {}
};
TreeNode* buildTreeRecursive(string& preorder, string& inorder,
int preStart, int inStart, int inEnd,
unordered_map<int, 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 = buildTreeRecursive(preorder, inorder, preStart + 1, inStart, rootIndex - 1, indexMap);
root->right = buildTreeRecursive(preorder, inorder, preStart + rootIndex - inStart + 1, rootIndex + 1, inEnd, indexMap);
return root;
}
// 根据前序遍历和中序遍历结果构造二叉树
TreeNode* buildTree(string& preorder, string& inorder) {
// 创建一个哈希表，用于快速查找中序遍历结果中节点值对应的索引
std::unordered_map<int, int> indexMap;
for (int i = 0; i < inorder.size(); ++i) {
indexMap[inorder[i]] = i;
}
// 递归构造二叉树
return buildTreeRecursive(preorder, inorder, 0, 0, inorder.size() - 1, indexMap);
}
// 后序遍历二叉树
void postorderTraversal(TreeNode* root) {
if (root == nullptr) {
return;
}
postorderTraversal(root->left);
postorderTraversal(root->right);
cout << root->val;
}
int main() {
string s;
while (getline(cin, s)) { // 接受一整行字符串
string preorder = "", inorder = "";
// 拆分出两个字符串
int i;
for (i = 0; s[i] != ' '; i++) preorder += s[i];
i++;
for (; i < s.size(); i++) inorder += s[i];
// 开始构造二叉树
TreeNode* root = buildTree(preorder, inorder);
postorderTraversal(root);
cout << endl;
}
return 0;
}
import java.util.*;
class TreeNode{
TreeNode left;
TreeNode right;
Character val;
public TreeNode(Character val) {
this.val = val;
}
}
public class Main{
public static Map<Character, Integer> map = new HashMap();
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (sc.hasNextLine()) {
String s = sc.nextLine();
String[] ss = s.split(" ");
String pre = ss[0];
String in = ss[1];
// 构建二叉树
// TreeNode preorder = build(pre.toCharArray());
// TreeNode inorder = build(in.toCharArray());
// 前序中序生成
TreeNode res = afterHelper(pre.toCharArray(), in.toCharArray());
//打印二叉树
printTree(res);
System.out.println();
}
}
public static TreeNode afterHelper(char[] pre, char[] in) {
for (int i = 0; i < in.length; i++) {
map.put(in[i], i);
}
TreeNode res = helper(pre, 0, pre.length - 1, in, 0, in.length - 1);
return res;
}
public static TreeNode helper(char[] pre, int ps, int pe, char[] in, int is, int ie) {
if (ps < 0 || ps > pe || is < 0 || is > ie) return null;
if (pe > pre.length - 1 || ie > in.length - 1) return null;
char headVal = pre[ps];
int headIndex = map.get(headVal);
int lengthOfLeft = headIndex - is;
TreeNode root = new TreeNode(headVal);
root.left = helper(pre, ps + 1, ps + lengthOfLeft,
in, is, headIndex - 1);
root.right = helper(pre, ps + 1 + lengthOfLeft, pe,
in, headIndex + 1, ie);
return root;
}
public static void printTree(TreeNode root) {
if (root == null) return;
printTree(root.left);
printTree(root.right);
System.out.print(root.val);
}
}class Node:
def __init__(self, val=None, left=None, right=None):
self.val = val
self.left = left
self.right = right
def build_tree(preorder, inorder):
if not preorder or not inorder:
return None
root_val = preorder[0]
root_index = inorder.index(root_val)
left_inorder = inorder[:root_index]
right_inorder = inorder[root_index+1:]
left_preorder = preorder[1:len(left_inorder)+1]
right_preorder = preorder[len(left_inorder)+1:]
root = Node(root_val)
root.left = build_tree(left_preorder, left_inorder)
root.right = build_tree(right_preorder, right_inorder)
return root
def postorder_traversal(root):
if not root:
return []
left = postorder_traversal(root.left)
right = postorder_traversal(root.right)
return left + right + [root.val]
while True:
try:
preorder, inorder = map(str, input().split())
if not preorder or not inorder:
break
root = build_tree(preorder, inorder)
postorder = postorder_traversal(root)
print(''.join(postorder))
except EOFError:
break package main
import (
"fmt"
"strings"
)
func main() {
for {
var preorder, inorder string
_, err := fmt.Scan(&preorder, &inorder)
if err != nil {
return
}
tree := buildTree(preorder, inorder, 0, len(preorder)-1, 0, len(inorder)-1)
fmt.Println(postorderTraversal(tree))
}
}
type TreeNode struct {
Val string
Left *TreeNode
Right *TreeNode
}
// 根据前序和中序遍历结果构造二叉树
func buildTree(preorder, inorder string, preStart, preEnd, inStart, inEnd int) *TreeNode {
if preStart > preEnd || inStart > inEnd {
return nil
}
//根节点值为前序遍历结果的第一个字符
root := &TreeNode{Val: string(preorder[preStart])}
// 在中序遍历结果中找到根节点的位置
var rootIndex int
for rootIndex = inStart; rootIndex <= inEnd; rootIndex++ {
if inorder[rootIndex] == preorder[preStart] {
break
}
}
// 递归构造左子树和右子树
leftTreeSize := rootIndex - inStart
root.Left = buildTree(preorder, inorder, preStart+1, preStart+leftTreeSize, inStart, rootIndex-1)
root.Right = buildTree(preorder, inorder, preStart+leftTreeSize+1, preEnd, rootIndex+1, inEnd)
return root
}
func postorderTraversal(root *TreeNode) string {
var res []string
var traversal func(node *TreeNode)
traversal = func(node *TreeNode) {
if node == nil {
return
}
traversal(node.Left)
traversal(node.Right)
res = append(res, node.Val)
}
traversal(root)
return strings.Join(res, "")
}#include <stdio.h>
#include <string.h>
// 定义二叉树节点结构
struct TreeNode {
char val;
struct TreeNode* left;
struct TreeNode* right;
};
// 根据前序和中序遍历结果构造二叉树
struct TreeNode* buildTree(char* preorder, char* inorder, int preStart, int preEnd, int inStart, int inEnd) {
if (preStart > preEnd || inStart > inEnd) {
return NULL;
}
// 根节点值为前序遍历结果的第一个字符
char rootValue = preorder[preStart];
struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
root->val = rootValue;
// 在中序遍历结果中找到根节点的位置
int rootIndex;
for (rootIndex = inStart; rootIndex <= inEnd; rootIndex++) {
if (inorder[rootIndex] == rootValue) {
break;
}
}
// 递归构造左子树和右子树
int leftTreeSize = rootIndex - inStart;
root->left = buildTree(preorder, inorder, preStart + 1, preStart + leftTreeSize, inStart, rootIndex - 1);
root->right = buildTree(preorder, inorder, preStart + leftTreeSize + 1, preEnd, rootIndex + 1, inEnd);
return root;
}
// 后序遍历二叉树并输出结果
void postorderTraversal(struct TreeNode* root) {
if (root == NULL) {
return;
}
postorderTraversal(root->left);
postorderTraversal(root->right);
printf("%c", root->val);
}
// 释放二叉树内存
void freeTree(struct TreeNode* root) {
if (root == NULL) {
return;
}
freeTree(root->left);
freeTree(root->right);
free(root);
}
int main() {
char preorder[100];
char inorder[100];
while (scanf("%s %s", preorder, inorder) == 2) {
int preLen = strlen(preorder);
int inLen = strlen(inorder);
// 构造二叉树
struct TreeNode* root = buildTree(preorder, inorder, 0, preLen - 1, 0, inLen - 1);
// 后序遍历并输出结果
postorderTraversal(root);
printf("\n");
// 释放内存
freeTree(root);
}
return 0;
}