LeetCode-105-从前序与中序遍历序列构造二叉树
1. 题目:
从前序与中序遍历序列构造二叉树
根据一棵树的前序遍历与中序遍历构造二叉树。
注意:
你可以假设树中没有重复的元素。
例如,给出
1 | 前序遍历 preorder = [3,9,20,15,7] |
返回如下的二叉树:
1 | 3 |
2. 解题:
我们知道,前序遍历是先遍历根节点,再遍历左子树,最后遍历右子树,因此我们知道前序遍历的顺序中第一个一定是根节点;
而中序遍历是先遍历左子树,再遍历根节点,最后遍历右子树,因此在中序遍历的顺序中找到根节点,则根节点前方就是左子树的中序遍历顺序,根节点后方就是右子树的遍历顺序。
简单来说:
前序遍历顺序 = 根节点 + 左子树的前序遍历 + 右子树的前序遍历;
中序遍历顺序 = 左子树的中序遍历 + 根节点 + 右子树的中序遍历;
那么前序遍历用来找“根节点”,中序遍历用来找左子树的个数和右子树的个数。
1 | 过程: |
代码:
1 | /** |