- 前序遍历为{根节点,{左孩子树},{右孩子树}},中序遍历为{{左孩子树},根节点,{右孩子树}}
- 可以从前序遍历拿出根节点(首位)确定中序遍历数组的根节点位置,从而划分左右子树在两序遍历数组的范围,接下来就是左右子树的构建过程,即将一个大问题分割成了相同类型但规模更小的子问题,直接递归解决。
public class Solution { public TreeNode reConstructBinaryTree(int[] pre, int[] in) { return reConstructBinaryTreeRec(pre, 0, pre.length - 1, in, 0, in.length - 1); } public TreeNode reConstructBinaryTreeRec(int[] pre, int preStart, int preEnd, int[] in, int inStart, int inEnd) { // 处理数组为空判断 if(preStart > preEnd || inStart > inEnd) { return null; } // 找出根节点 int rootPosition = inStart - 1; while(++rootPosition <= inEnd) { if(pre[preStart] == in[rootPosition]) { break; } } // 建立根节点并给构建左右孩子节点 TreeNode root = new TreeNode(pre[preStart]); root.left = reConstructBinaryTreeRec(pre, preStart + 1, preStart + rootPosition - inStart, in, inStart, rootPosition - 1); root.right = reConstructBinaryTreeRec(pre, preStart + rootPosition - inStart + 1, preEnd, in, rootPosition + 1, inEnd); return root; } }