# 【面试】重建二叉树

## 一、描述

class BinaryTreeNode {
int m_nValue;
BinaryTreeNode m_pLeft;
BinaryTreeNode m_pRight;
public BinaryTreeNode(int m_nValue, BinaryTreeNode m_pLeft, BinaryTreeNode m_pRight) {
this.m_nValue = m_nValue;
this.m_pLeft = m_pLeft;
this.m_pRight = m_pRight;
}
}

## 三、代码

package com.hust.grid.leesf.chapter2;
import java.util.Scanner;
class BinaryTreeNode {
int m_nValue;
BinaryTreeNode m_pLeft;
BinaryTreeNode m_pRight;
public BinaryTreeNode(int m_nValue, BinaryTreeNode m_pLeft, BinaryTreeNode m_pRight) {
this.m_nValue = m_nValue;
this.m_pLeft = m_pLeft;
this.m_pRight = m_pRight;
}
}
public class ConstructBinaryTree {
public static BinaryTreeNode construct(int[] preOrder, int[] inOrder, int length) throws Exception {
if (preOrder == null || inOrder == null || length <= 0) {
return null;
}
return constructCore(preOrder, 0, preOrder.length - 1, inOrder, 0, inOrder.length - 1);
}
public static BinaryTreeNode constructCore(int[] preOrder, int startPreIndex, int endPreIndex,
int[] inOrder, int startInIndex, int endInIndex) throws Exception {
int rootValue = preOrder[startPreIndex];
BinaryTreeNode root = new BinaryTreeNode(rootValue, null, null);
// 只有一个元素，为递归的出口
if (startPreIndex == endPreIndex) {
if (startInIndex == endInIndex
&& preOrder[startPreIndex] == inOrder[startInIndex]) {
return root;
} else {
throw new Exception("invalid input");
}
}
// 在中序遍历中找到根结点
int rootInIndex = startInIndex;
while (rootInIndex <= endInIndex && inOrder[rootInIndex] != rootValue) {
++rootInIndex;
}
if (rootInIndex == endInIndex && inOrder[rootInIndex] != rootValue) {
throw new Exception("invalid input");
}
int leftLength = rootInIndex - startInIndex;
int leftPreOrderEndIndex = startPreIndex + leftLength;
if (leftLength > 0) {
// 构建左子树
root.m_pLeft = constructCore(preOrder, startPreIndex + 1,
leftPreOrderEndIndex, inOrder, startInIndex,
rootInIndex - 1);
}
if (leftLength < endPreIndex - startPreIndex) {
// 右子树存在元素,构建右子树
root.m_pRight = constructCore(preOrder, leftPreOrderEndIndex + 1,
endPreIndex, inOrder, rootInIndex + 1, endInIndex);
}
return root;
}
public static void main(String[] args) throws Exception {
Scanner scan = new Scanner(System.in);
String preOrderInput = scan.nextLine();
String inOrderInput = scan.nextLine();
int[] preOrder = new int[preOrderInput.length()];
int[] inOrder = new int[inOrderInput.length()];
for (int index = 0; index < preOrderInput.length(); index++) {
preOrder[index] =  Integer.parseInt(String.valueOf(preOrderInput.charAt(index)));
}
for (int index = 0; index < inOrderInput.length(); index++) {
inOrder[index] = Integer.parseInt(String.valueOf(inOrderInput.charAt(index)));
}
BinaryTreeNode root = construct(preOrder, inOrder, preOrder.length);
preOrderTraverse(root);
System.out.println();
inOrderTraverse(root);
System.out.println();
postOrderTraverse(root);
}
public static void preOrderTraverse(BinaryTreeNode root) {
if (root != null) {
System.out.print(root.m_nValue + " ");
preOrderTraverse(root.m_pLeft);
preOrderTraverse(root.m_pRight);
}
}
public static void inOrderTraverse(BinaryTreeNode root) {
if (root != null) {
inOrderTraverse(root.m_pLeft);
System.out.print(root.m_nValue + " ");
inOrderTraverse(root.m_pRight);
}
}
public static void postOrderTraverse(BinaryTreeNode root) {
if (root != null) {
postOrderTraverse(root.m_pLeft);
postOrderTraverse(root.m_pRight);
System.out.print(root.m_nValue + " ");
}
}
}

12473568
47215386

1 2 4 7 3 5 6 8
4 7 2 1 5 3 8 6
7 4 2 5 8 6 3 1 

|
2月前

33 0
|
2月前

24 0
|
2月前
【一刷《剑指Offer》】面试题 23：从上往下打印二叉树
【一刷《剑指Offer》】面试题 23：从上往下打印二叉树
37 0
|
2月前
【一刷《剑指Offer》】面试题 19：二叉树的镜像
【一刷《剑指Offer》】面试题 19：二叉树的镜像
24 0
|
2月前
【一刷《剑指Offer》】面试题 6：重建二叉树
【一刷《剑指Offer》】面试题 6：重建二叉树
23 0
|
2月前
|

24 0
|
2月前
|

30 0
|
2月前
【面试小知识】带你深入了解二叉树的前中序遍历
【面试小知识】带你深入了解二叉树的前中序遍历
30 0
|
2月前
|

【Java程序员面试专栏 数据结构篇】五 高频面试算法题：二叉树
【Java程序员面试专栏 数据结构篇】五 高频面试算法题：二叉树
45 0
|
7月前
|

LeetCode | 二叉树高频面试算法题汇总【速来】-2
LeetCode | 二叉树高频面试算法题汇总【速来】
42 0