每日一题 2019 - 04 - 24
题目:
Given inorder and postorder traversal of a tree, construct the binary tree.
Note:
You may assume that duplicates do not exist in the tree.
For example, given
1 | inorder = [9,3,15,20,7] |
Return the following binary tree:
1 | 3 |
解法:
这个题给出二叉树的中序遍历和后续遍历让还原出原先的二叉树,思路大概如下:
- 后续遍历的最后一个结点为二叉树的根节点,找出根节点,在中序遍历中根据根节点将中序遍历分为左子树与右子树
- 在中序遍历分开后的左子树右子树中继续进行划分,同时将后续遍历的序列也进行划分
递归这个过程即可完成还原;
代码:
1 | /** |