cyufeng
2018-11-18 16:37:03
二叉树问题
输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列 {1,2,4,7,3,5,6,8} 和中序遍历序列{4,7,2,1,5,3,8,6},则重建二叉树并返回。
问题解析:
前序遍历:中左右,中序遍历:左中右。
先序遍历的第一个值就是根节点,即是1,再从中序遍历的中找到这个根节点,那么这个数前面的数字就是左分支,后面的数字就是右分支。
按照这个思路,运用递归的方法解决问题;
** * Definition for binary tree * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public static void main(String[] args) { int[] pre = {1, 2, 4, 7, 3, 5, 6, 8};//前 int[] in = {4, 7, 2, 1, 5, 3, 8, 6};//中 TreeNode treeNode = reConstructBinaryTree(pre, in); // TreeNode treeNode = reConstructBinaryTree(pre,in); System.out.println(treeNode.toString()); } public static TreeNode reConstructBinaryTree(int[] pre, int[] in) { TreeNode treeNode = new TreeNode(pre[0]); int index = 0; for (int i = 0; i < in.length; i++) { if (pre[0] == in[i]) index = i; } //分离前序遍历结果 int[] preL = new int[index]; int[] preR = new int[pre.length - 1 - index]; for (int i = 0; i < index; i++) {//复制根节点左侧数字,并且抛弃第一个数字 preL[i] = pre[i + 1]; } for (int i = 0; i < pre.length - 1 - index; i++) {//复制根节点右侧数字 preR[i] = pre[index + 1 + i]; } // 分离中序遍历结果 int[] inL = new int[index]; int[] inR = new int[in.length - 1 - index]; for (int i = 0; i < index; i++) {//复制根节点左侧数字 inL[i] = in[i]; } for (int i = 0; i < in.length - 1 - index; i++) {//复制根节点右侧数字 inR[i] = in[index + 1 + i]; } if (in.length > 0 & pre.length > 0) { if (preL.length > 0) { treeNode.left = reConstructBinaryTree(preL, inL); } if (preR.length > 0) { treeNode.right = reConstructBinaryTree(preR, inR); } } return treeNode; } } public class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val = x; } }
评论
最近浏览
最代码官方 LV167
2018年11月18日