21. 构造二叉树

C++

#include <iostream>
#include <unordered_map>
#include <string>
using namespace std;

// 定义二叉树节点结构
struct TreeNode {
    char val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(char 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;
}

Java

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);
    }
     
     
}

python


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

Go

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, "")
}

Js

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;
  }
  postOrder(){
    if(this.left!=null) this.left.postOrder();
    if(this.right!=null) this.right.postOrder();
    out.write(this.data);
  }
}

function createBTree(preOrder,inOrder,preLeft,preRight,inLeft,inRight){
  if(preLeft>preRight||inLeft>inRight) return null;
  let root=new Node(preOrder[preLeft]);
  let rootIndex=inOrder.indexOf(preOrder[preLeft]);
  let leftNum=rootIndex-inLeft;
  let rightNum=inRight-rootIndex;
  root.left=createBTree(preOrder,inOrder,preLeft+1,preLeft+leftNum,inLeft,rootIndex-1);
  root.right=createBTree(preOrder,inOrder,preLeft+leftNum+1,preRight,rootIndex+1,inRight);
  return root;
}

async function main(){
  while(line=await readline()){
    [preOrder,inOrder]=line.split(" ");
    const root=createBTree(preOrder,inOrder,0,preOrder.length-1,0,inOrder.length-1);
    root.postOrder();
    console.log();
  }
}

main();

C

#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;
}

programmercarl / kamacoder-solutions

21. 构造二叉树

C++

Java

python

Go

Js

C

简介

发行版

贡献者

近期动态

programmercarl / kamacoder-solutions .gitee-modal { width: 500px !important; }

21. 构造二叉树

C++

Java

python

Go

Js

C

简介

发行版

贡献者

近期动态

搜索帮助

programmercarl / kamacoder-solutions