Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
package com.vamdt.fox.fox.of;
import java.util.HashMap;
import java.util.Map;
/**
* pre arr + in arr => tree
* in arr + post arr => tree
* pre arr + post arr => tree
*/
public class ReConstructBinaryTree {
public static class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
public static void main(String[] args) {
int[] pre = new int[] {1,2,4,7,3,5,6,8};
int[] in = new int[] {4,7,2,1,5,3,8,6};
int[] post = new int[] {7,4,2,5,8,6,3,1};
ReConstructBinaryTree test = new ReConstructBinaryTree();
// TreeNode head = test.reConstructBinaryTreeByInAndPost(post, in);
TreeNode head = test.reConstructBinaryTreeByPreAndPost(new int[]{1,2,4,5,3,6,7}, new int[]{4,5,2,6,7,3,1});
printTreePre(head);
System.out.println();
printTreeIn(head);
System.out.println();
printTreePost(head);
System.out.println();
}
public static void printTreePre(TreeNode node) {
if (node == null) {
return;
}
System.out.print(node.val);
System.out.print(' ');
printTreePre(node.left);
printTreePre(node.right);
}
public static void printTreeIn(TreeNode node) {
if (node == null) {
return;
}
printTreeIn(node.left);
System.out.print(node.val);
System.out.print(' ');
printTreeIn(node.right);
}
public static void printTreePost(TreeNode node) {
if (node == null) {
return;
}
printTreePost(node.left);
printTreePost(node.right);
System.out.print(node.val);
System.out.print(' ');
}
// 先序和中序构造二叉树
public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
if (pre == null || in == null) {
return null;
}
Map<Integer, Integer> helpMap = new HashMap<>();
for (int i = 0; i < in.length; i++) {
helpMap.put(in[i], i);
}
return reConstructBinaryTree(pre, helpMap, 0, pre.length - 1, 0, in.length - 1);
}
private TreeNode reConstructBinaryTree(int[] pre, Map<Integer, Integer> helpMap, int preLeft, int preRight, int inLeft, int inRight) {
// 子树大小为负,子树为空
if (preLeft > preRight) {
return null;
}
TreeNode treeNode = new TreeNode(pre[preLeft]);
int inIndex = helpMap.get(treeNode.val);
// 中序索引 - 先序索引 = 左子树大小
int leftTreeSize = inIndex - inLeft;
treeNode.left = reConstructBinaryTree(pre, helpMap, preLeft + 1, preLeft + leftTreeSize, inLeft, inIndex -1);
treeNode.right = reConstructBinaryTree(pre, helpMap, preLeft + leftTreeSize + 1, preRight, inIndex + 1, inRight);
return treeNode;
}
// 中序和后序构造二叉树
public TreeNode reConstructBinaryTreeByInAndPost(int [] post, int [] in) {
if (post == null || in == null) {
return null;
}
Map<Integer, Integer> helpMap = new HashMap<>();
for (int i = 0; i < in.length; i++) {
helpMap.put(in[i], i);
}
return reConstructBinaryTreeByInAndPost(post, helpMap, 0, post.length - 1, 0, in.length - 1);
}
private TreeNode reConstructBinaryTreeByInAndPost(int[] post, Map<Integer, Integer> helpMap, int postLeft, int postRight, int inLeft, int inRight) {
// 子树大小为负,子树为空
if (postLeft > postRight) {
return null;
}
TreeNode treeNode = new TreeNode(post[postRight]);
int inIndex = helpMap.get(treeNode.val);
// 中序索引 - 先序索引 = 左子树大小
int leftTreeSize = inIndex - inLeft;
treeNode.left = reConstructBinaryTreeByInAndPost(post, helpMap, postLeft, postLeft + leftTreeSize - 1, inLeft, inIndex -1);
treeNode.right = reConstructBinaryTreeByInAndPost(post, helpMap, postLeft + leftTreeSize, postRight - 1, inIndex + 1, inRight);
return treeNode;
}
// 先序和后序构造二叉树,只有在非叶节点都有左孩子和右孩子的情况下,才可以构造成整颗树
// 以下不能准确构造出二叉树, 左右两颗树的先序都为[1,2],后序都为[2,1]
// 1 1
// / \
// 2 2
//
public TreeNode reConstructBinaryTreeByPreAndPost(int [] pre, int [] post) {
if (pre == null || post == null) {
return null;
}
Map<Integer, Integer> helpMap = new HashMap<>();
for (int i = 0; i < post.length; i++) {
helpMap.put(post[i], i);
}
return reConstructBinaryTreeByPreAndPost(pre, helpMap, 0, pre.length - 1, 0, post.length - 1);
}
private TreeNode reConstructBinaryTreeByPreAndPost(int[] pre, Map<Integer, Integer> helpMap, int preLeft, int preRight, int postLeft, int postRight) {
// 左 == 右,遇到叶节点,返回
TreeNode treeNode = new TreeNode(pre[preLeft]);
if (preLeft == preRight) {
return treeNode;
}
int leftTreeNodePostIndex = helpMap.get(pre[++preLeft]);
int leftTreeSize = leftTreeNodePostIndex - postLeft;
treeNode.left = reConstructBinaryTreeByPreAndPost(pre, helpMap, preLeft, preLeft + leftTreeSize, postLeft, leftTreeNodePostIndex);
treeNode.right = reConstructBinaryTreeByPreAndPost(pre, helpMap, preLeft + leftTreeSize + 1, preRight, leftTreeNodePostIndex + 1, postRight -1);
return treeNode;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.