题目
根据树的前序、中序遍历构建出树结构
题解
什么是前序、中序我就不带大家复习了 根左右 左根右。
可爱的小树
前序遍历 [3,9,20,15,7]
中序遍历 [9,3,15,20,7]
- 根据前序遍历特点 我们能立刻得知，前序遍历的第一个元素，即是这棵树的根节点root节点，前序遍历中 我们可以粗略把数组内容分成3段：根、所有左元素、所有右元素（黄根、绿左、蓝右）。
前序分隔
- 前序遍历中，root节点的下一个节点即是第一个左孩子（即节点9），那第一个右孩子呢？
- 其实只要能够计算出左元素个数我们就能根据root节点计算出第一个右孩子在前序遍历中的相对位置 即
root节点下标+ 左元素个数 +1即是第一个右孩子下标
中序分隔
- root节点下标是前序的第一个元素，那左元素个数我们怎么计算呢？我们不妨找到根节点在中序遍历中的下标 他的左侧即是全部左元素，他的右侧即是全部右元素。例如上图：我们根据中序可以发现root节点 3左侧有1个元素，那么在前序遍历中，从根节点数起，向后数2位，即是第一个右子树元素。
- 此时，我们已经能够构建、获取树的root、第一个左、第一个右，我们只要把第一个左、第一个右当作是新的root，进行上述逻辑的递归，即可构建出完整的树。
- 但是有一点需要注意，在根据中序计算左右元素数量的时候应当控制元素边界，每次以root将中序数组分割成3部分，全部左、root、全部右。
private int [] preorder;
private Map<Integer,Integer> map;
public TreeNode buildTree(int[] preorder, int[] inorder) {
this.preorder = preorder;
map = new HashMap<>(inorder.length);
for (int i=0;i<inorder.length;i++) map.put(inorder[i],i);
return buildTree(0,0,preorder.length-1);
}
private TreeNode buildTree(int rootIndexForPre,int startIndexForIn,int endIndexForIn){
if(startIndexForIn>endIndexForIn) return null;
TreeNode root = new TreeNode(preorder[rootIndexForPre]);
int rootIndexForIn = map.get(preorder[rootIndexForPre]);
root.setLeft(buildTree(rootIndexForPre+1,startIndexForIn,rootIndexForIn-1));
root.setRight(buildTree(rootIndexForIn-startIndexForIn+rootIndexForPre+1,rootIndexForIn+1,endIndexForIn));
return root;
}
源码: 剑指offer4J
