题目链接
代码随想录算法讲解
#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;
struct TreeNode {
char val;
TreeNode* left;
TreeNode* right;
TreeNode(char val) : val(val), left(nullptr), right(nullptr) {}
};
// 根据输入数据构造二叉树
TreeNode* buildTree(unordered_map<char, pair<char, char>>& nodeMap, char rootValue) {
if (rootValue == '0') {
return nullptr;
}
TreeNode* root = new TreeNode(rootValue);
int leftChild = nodeMap[rootValue].first;
int rightChild = nodeMap[rootValue].second;
root->left = buildTree(nodeMap, leftChild);
root->right = buildTree(nodeMap, rightChild);
return root;
}
// 前序遍历二叉树
void preorderTraversal(TreeNode* root) {
if (root == nullptr) {
return;
}
cout << root->val;
preorderTraversal(root->left);
preorderTraversal(root->right);
}
// 中序遍历二叉树
void inorderTraversal(TreeNode* root) {
if (root == nullptr) {
return;
}
inorderTraversal(root->left);
cout << root->val;
inorderTraversal(root->right);
}
// 后序遍历二叉树
void postorderTraversal(TreeNode* root) {
if (root == nullptr) {
return;
}
postorderTraversal(root->left);
postorderTraversal(root->right);
cout << root->val;
}
int main() {
int n;
cin >> n;
unordered_map<char, std::pair<char, char>> nodeMap;
// 先保存输入的数据
vector<char> index = vector<char>(n + 1, '0');
vector<vector<int>> nums = vector<vector<int>>(n + 1, vector<int>(2, 0));
for (int i = 1; i <= n; i++) {
cin >> index[i] >> nums[i][0] >> nums[i][1];
}
// 生成二叉树
for (int i = 1; i <= n; i++) {
nodeMap[index[i]] = make_pair(index[nums[i][0]], index[nums[i][1]]);
}
TreeNode* root = buildTree(nodeMap, index[1]);
preorderTraversal(root);
cout << std::endl;
inorderTraversal(root);
cout << std::endl;
postorderTraversal(root);
cout << std::endl;
return 0;
}
import java.util.*;
class TreeNode {
char val;
TreeNode left;
TreeNode right;
public TreeNode(char val) {
this.val = val;
}
}
public class Main{
static TreeNode[] nodes = new TreeNode[30];
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (sc.hasNextInt()) {
int len = sc.nextInt();
for (int i = 0; i < len; i++) {
// F23
char val = sc.next().charAt(0);
int left = sc.nextInt();
int right = sc.nextInt();
if (nodes[i + 1] == null) {
nodes[i + 1] = new TreeNode(val);
} else {
nodes[i + 1].val = val;
}
// 说明有左节点
if (left != 0) {
if (nodes[left] == null) {
nodes[left] = new TreeNode('\0');
}
nodes[i + 1].left = nodes[left];
}
if (right != 0) {
if (nodes[right] == null) {
nodes[right] = new TreeNode('\0');
}
nodes[i + 1].right = nodes[right];
}
}
preorder(nodes[1]);
System.out.println();
inorder(nodes[1]);
System.out.println();
postorder(nodes[1]);
System.out.println();
}
}
public static void preorder(TreeNode root) {
if (root == null) return;
System.out.print(root.val);
preorder(root.left);
preorder(root.right);
}
public static void inorder(TreeNode root) {
if (root == null) return;
inorder(root.left);
System.out.print(root.val);
inorder(root.right);
}
public static void postorder(TreeNode root) {
if (root == null) return;
postorder(root.left);
postorder(root.right);
System.out.print(root.val);
}
}// 方法二：使用索引，简化构建树的过程
import java.util.Scanner;
public class Main {
static class TreeNode {
char val;
int left;
int right;
public TreeNode(char val, int left, int right) {
this.val = val;
this.left = left;
this.right = right;
}
}
static TreeNode[] nodes;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
nodes = new TreeNode[n + 1];
for (int i = 0; i < n; i++) {
char val = sc.next().charAt(0);
int left = sc.nextInt();
int right = sc.nextInt();
nodes[i + 1] = new TreeNode(val, left, right);
}
preOrderTraversal(1);
System.out.println();
inOrderTraversal(1);
System.out.println();
postOrderTraversal(1);
System.out.println();
sc.close();
}
private static void postOrderTraversal(int root) {
if (root == 0)
return;
postOrderTraversal(nodes[root].left);
postOrderTraversal(nodes[root].right);
System.out.print(nodes[root].val);
}
private static void inOrderTraversal(int root) {
if (root == 0)
return;
inOrderTraversal(nodes[root].left);
System.out.print(nodes[root].val);
inOrderTraversal(nodes[root].right);
}
private static void preOrderTraversal(int root) {
if (root == 0)
return;
System.out.print(nodes[root].val);
preOrderTraversal(nodes[root].left);
preOrderTraversal(nodes[root].right);
}
}class Node:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def preorder(root):
if not root:
return []
left = preorder(root.left)
right = preorder(root.right)
return [root.val] + left + right
def inorder(root):
if not root:
return []
left = inorder(root.left)
right = inorder(root.right)
return left + [root.val] + right
def postorder(root):
if not root:
return []
left = postorder(root.left)
right = postorder(root.right)
return left + right + [root.val]
n = int(input())
nodes = [None] * (n + 1)
line_in = []
for i in range(n):
line = input().split()
val, left, right = line[0], int(line[1]), int(line[2])
if not nodes[i+1]:
node = Node(val)
nodes[i + 1] = node
else:
# 更新val
nodes[i + 1].val = val
if left != 0:
# 创建一个node,放入nodes列表
node_left = Node('x')
nodes[left] = node_left
nodes[i + 1].left = node_left
if right != 0:
node_right = Node('x')
nodes[right] = node_right
nodes[i + 1].right = node_right
root = nodes[1]
pre = preorder(root)
ino = inorder(root)
post = postorder(root)
print(''.join(pre))
print(''.join(ino))
print(''.join(post))package main
import (
"fmt"
"strings"
)
type Node struct {
Val string
Left *Node
Right *Node
}
func preorder(root *Node) []string {
if root == nil {
return []string{}
}
left := preorder(root.Left)
right := preorder(root.Right)
return append([]string{root.Val}, append(left, right...)...)
}
func inorder(root *Node) []string {
if root == nil {
return []string{}
}
left := inorder(root.Left)
right := inorder(root.Right)
return append(append(left, root.Val), right...)
}
func postorder(root *Node) []string {
if root == nil {
return []string{}
}
left := postorder(root.Left)
right := postorder(root.Right)
return append(append(left, right...), root.Val)
}
func main() {
var n int
fmt.Scan(&n)
nodes := make([]*Node, n+1)
var line string
for i := 0; i < n; i++ {
fmt.Scan(&line)
val := line[0:1]
left, right := 0, 0
fmt.Scan(&left, &right)
if nodes[i+1] == nil {
node := &Node{Val: val}
nodes[i+1] = node
} else {
nodes[i+1].Val = val
}
if left != 0 {
nodeLeft := &Node{Val: "x"}
nodes[left] = nodeLeft
nodes[i+1].Left = nodeLeft
}
if right != 0 {
nodeRight := &Node{Val: "x"}
nodes[right] = nodeRight
nodes[i+1].Right = nodeRight
}
}
root := nodes[1]
pre := preorder(root)
ino := inorder(root)
post := postorder(root)
fmt.Println(strings.Join(pre, ""))
fmt.Println(strings.Join(ino, ""))
fmt.Println(strings.Join(post, ""))
}
#include <stdio.h>
#include <stdlib.h>
typedef struct inNode{
char val;
int left;
int right;
}inNode;
typedef struct TreeNode{
char val;
struct TreeNode* left;
struct TreeNode* right;
}TreeNode;
//构建二叉树
TreeNode* buildTree(inNode* nums, int index ) {
if( index == 0) {
return NULL;
}
//递归构建二叉树
TreeNode* ptree = (TreeNode*)malloc(sizeof(TreeNode));
ptree->val = nums[index].val;
ptree->left = buildTree( nums, nums[index].left );
ptree->right = buildTree( nums, nums[index].right );
return ptree;
}
//前序遍历
void preorderTraversal(TreeNode* ptree) {
if (ptree == NULL) {
return;
}
printf("%c", ptree->val);
preorderTraversal(ptree->left);
preorderTraversal(ptree->right);
}
// 中序遍历二叉树
void inorderTraversal(TreeNode* ptree) {
if (ptree == NULL) {
return;
}
inorderTraversal(ptree->left);
printf("%c", ptree->val);
inorderTraversal(ptree->right);
}
// 后序遍历二叉树
void postorderTraversal(TreeNode* ptree) {
if (ptree == NULL) {
return;
}
postorderTraversal(ptree->left);
postorderTraversal(ptree->right);
printf("%c", ptree->val);
}
int main()
{
int n;
scanf("%d\n", &n);
// 保存输入的数据
inNode* nums = (inNode*)malloc( sizeof(inNode) * (n+1) );
int i = 1;
for ( ; i <= n; i++ ){
scanf("%c %d %d", &(nums[i].val), &(nums[i].left), &(nums[i].right) );
//处理换行
if (i < n){
getchar();
}
}
TreeNode* root = buildTree(nums, 1);
preorderTraversal(root);
printf("\n");
inorderTraversal(root);
printf("\n");
postorderTraversal(root);
printf("\n");
return 0;
}