LeetCode里面的两道题：分别是根据前序遍历中序遍历求树的结构，另外一个类似的题是根据中序遍历后序遍历求树的结构。
对于这种经典的题，自然有经典的解题思路。二话不说，直接上代码，具体的解题思路，
1.树节点的定义
public class TreeNode {
public int data;
public TreeNode left;
public TreeNode right;
public TreeNode(int data) {
this.data = data;
this.left = null;
this.right = null;
}
}
2.遍历树的相关代码
public class VisitTree {
public static void preVisit(TreeNode root) {
if(root == null) {
return;
}
System.out.print(root.data + " ");
preVisit(root.left);
preVisit(root.right);
}
public static void inVisit(TreeNode root) {
if(root == null) {
return;
}
inVisit(root.left);
System.out.print(root.data + " ");
inVisit(root.right);
}
public static void postVisit(TreeNode root) {
if(root == null) {
return;
}
postVisit(root.left);
postVisit(root.right);
System.out.print(root.data + " ");
}
}
3.根据前序遍历中序遍历确定树的结构
/**
* 我们先考察先序遍历序列和中序遍历序列的特点。
* 对于先序遍历序列，根在最前面，后面部分存在一个分割点，前半部分是根的左子树，后半部分是根的右子树。
* 对于中序遍历序列，根在中间部分，从根的地方分割，前半部分是根的左子树，后半部分是根的右子树。
* 当我们从上向下构建树时，我们可以通过先序遍历序列知道根节点的值，但是如何知道两个序列是在哪里分割的呢？这就要依靠中序序列了。
* 我们在中序序列中找到这个根的值，根据这个根的坐标，我们可以知道这个根左子树有多少个节点，右子树有多少个节点。
* 然后我们根据这个将先序遍历序列分割，通过递归再次取每个部分的第一个作为根，
* 同时为了下一次能准确的计算出左右子树各有多少节点，我们也要同时对中序遍历序列进行分割。
*
*/
public class PreInOrder {
public static int preStart = 0;
public static TreeNode buildTree(int[] preorder, int[] inorder) {
if(preorder.length == 0 || inorder.length == 0) return null;
return helper(0, inorder.length - 1, preorder, inorder);
}
private static TreeNode helper(int inStart, int inEnd, int[] preorder, int[] inorder) {
if(preStart > preorder.length || inStart > inEnd) {
return null;
}
TreeNode root = new TreeNode(preorder[preStart]);
int inMid = 0;
// 找到根在中序序列中的位置，从而知道先序中的分割点
for(int i=inStart; i<=inEnd; i++) {
if(inorder[i] == preorder[preStart]) {
inMid = i;
}
}
preStart++;
// 例如先序序列 1(234)(567) 中2是左子树的根
root.left = helper(inStart, inMid - 1, preorder, inorder);
// 先序序列 1(234)(567) 中5是右子树的根
root.right = helper(inMid + 1, inEnd, preorder, inorder);
return root;
}
public static void main(String[] args) {
int[] preorder = {1,2,4,6,7,3,5};
int[] inorder = {4,6,7,2,1,5,3};
TreeNode root = buildTree(preorder, inorder);
VisitTree.preVisit(root);
System.out.println();
VisitTree.inVisit(root);
System.out.println();
VisitTree.postVisit(root);
}
4.根据中序遍历后序遍历确定树的结构
/**
* 中序序列仍然是以根节点划分为左右两边，而后序序列的特点则是根在最后，然后在跟前面的那部分中，前面部分是左子树，后面的部分是右子树。
* 所以其实我们就是把上一题给反过来了。
* 这题我们将后序序列的指针全局化，这样我们可以先建好右子树，再建左子树，而指针只要顺序从后向前就行了。
*/
public class PostInOrder {
public static int postEnd = 0;
public static TreeNode buildTree(int[] postorder, int[] inorder) {
postEnd = postorder.length - 1;
return helper(0, inorder.length - 1, postorder, inorder);
}
private static TreeNode helper(int inStart, int inEnd, int[] postorder, int[] inorder) {
if(postEnd < 0 || inStart > inEnd) {
return null;
}
TreeNode root = new TreeNode(postorder[postEnd--]);
int inMid = 0;
for(int i=inStart; i<=inEnd; i++) {
if(inorder[i] == root.data) {
inMid = i;
break;
}
}
root.right = helper(inMid + 1, inEnd, postorder, inorder);
root.left = helper(inStart, inMid - 1, postorder, inorder);
return root;
}
public static void main(String[] args) {
int[] inorder = {4,6,7,2,1,5,3};
int[] postorder = {7,6,4,2,5,3,1};
TreeNode root = buildTree(postorder, inorder);
VisitTree.preVisit(root);
System.out.println();
VisitTree.inVisit(root);
System.out.println();
VisitTree.postVisit(root);
}
}
