题解 | #二叉搜索树的后序遍历序列#
重建二叉树
http://www.nowcoder.com/practice/8a19cbe657394eeaac2f6ea9b0f6fcf6
{java}递归思路:
1、前序:序列的第一个值一定是整个树的根节点;
2、后续:根节点左边的值全部的都是在树的左子节点这一边,根节点右边的值都在树的右子节点这一边;
3、根据1和2可以判断树的根节点并将左右子树分开;
4、左右子树同样符合1、2两点,将左右子序列递归即可;
import java.util.*; public class Solution { public TreeNode reConstructBinaryTree(int [] pre,int [] vin) { if(pre.length == 0) return null; if(pre.length == 1) return new TreeNode(pre[0]); int index = 0; for (; index < vin.length; index++){ if(vin[index] == pre[0] ){ break; } } TreeNode head = new TreeNode(pre[0]); head.left = reConstructBinaryTree( Arrays.copyOfRange(pre,1,index + 1), Arrays.copyOfRange(vin,0,index) ); head.right = reConstructBinaryTree( Arrays.copyOfRange(pre,index + 1,pre.length), Arrays.copyOfRange(vin,index + 1,vin.length) ); return head; } }