题目描述:
输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6},则重建二叉树并返回。
思路
第一种思路
二叉树的前序遍历是先遍历根节点,先序遍历左子树,先序遍历右子树;
二叉树的中序遍历,中序遍历左子树,遍历根节点,中序遍历右子树;
所以我们试图找到这样一个规律,先序遍历是以根节开始的,不管是左子树还是右子树,开头都一定根节点。中序遍历是以左子树,根节点,右子树这样形成的,可以通过中序遍历实现区分左右子树。
代码实现
第一种思路
这是我实现的思路,不是很简洁,比较冗余,但是没有使用其他的一些库来辅助,有一定的借鉴意义把,哈哈哈
public class Main { 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}; TreeNode treeNode = reConstructBinaryTree(pre,in); preTreeNode(treeNode); } public static TreeNode reConstructBinaryTree(int [] pre,int [] in) { TreeNode treeNodepre = null; if(pre.length>0) { treeNodepre = new TreeNode(pre[0]); int index=0; for(int j=0;j<in.length;j++) { if(in[j] == pre[0]) index = j; } int[] leftlist = new int[index]; int[] prerootleft = new int[index]; int[] rightlist = new int[in.length-index-1 <0 ? 0: in.length-index-1]; int[] prerootright = new int[rightlist.length]; for(int j=0;j<index;j++) { leftlist[j] = in[j]; prerootleft[j] = pre[j+1]; } treeNodepre.left = reConstructBinaryTree(prerootleft,leftlist); for(int j=index+1;j<in.length;j++) { rightlist[j-index-1] = in[j]; prerootright[j-index-1] = pre[j]; } treeNodepre.right = reConstructBinaryTree(prerootright,rightlist); } return treeNodepre; } public static void preTreeNode( TreeNode treeNode ) { if(treeNode != null) { preTreeNode(treeNode.left); System.out.println(treeNode.val); preTreeNode(treeNode.right); }
} } class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val = x; } }
|
牛客上面大佬是如何实现的:代码简洁,但是思路是一样的,就是太简洁了,膜拜膜拜,我还是对二叉树的理解不是很充分导致代码不够简洁。
import java.util.*;
public class Solution { public TreeNode reConstructBinaryTree(int [] pre,int [] in) { if(pre.length == 0||in.length == 0){ return null; } TreeNode node = new TreeNode(pre[0]); for(int i = 0; i < in.length; i++){ if(pre[0] == in[i]){ node.left = reConstructBinaryTree(Arrays.copyOfRange(pre, 1, i+1), Arrays.copyOfRange(in, 0, i)); node.right = reConstructBinaryTree(Arrays.copyOfRange(pre, i+1, pre.length), Arrays.copyOfRange(in, i+1,in.length)); } } return node; } }
|