每天做一道算法题,循序渐进,按算法分类刷题。坚持下去,看能坚持多久,也看最终能有多大成效。
从前序与中序遍历序列构造二叉树
根据一棵树的前序遍历与中序遍历构造二叉树。
注意:你可以假设树中没有重复的元素。
例如,给出
<code>前序遍历 preorder = [3,9,20,15,7] 中序遍历 inorder = [9,3,15,20,7]/<code>
返回如下的二叉树:
<code> 3 / \ 9 20 / \ 15 7/<code>
解决方案
通过前序遍历可以确定根节点以及左子树的根节点,拿到根节点之后可以去中序遍历里面确定左子树数目和右子树数目,从而可以在前序遍历里面确认右子树的根节点。然后递归构建树。