根据遍历结果重构二叉树

Question

老师你好，通过递归实现二叉树的前中后序遍历很简单直观。但是可以通过遍历结果重构二叉树吗？
如果前序遍历[1, 2, NULL, NULL, 3, 4, NULL, NULL, 5, NULL, NULL], 如果构建二叉树；
或者后序遍历[NULL,NULL,2,NULL,NULL,4,NULL,NULL,5,3,1,]，又该如何构建二叉树？

Answer 1

liuyubobobo 2020-04-21 12:32:30

你的问题基本就是 Leetcode 297 号问题的反序列化的步骤。如果使用 bfs，就是层序遍历的方式，如果使用 dfs，就是前序遍历的方式。题解中有很多详细的讲解，可以研究一下看看？

中文版传送门：https://leetcode-cn.com/problems/serialize-and-deserialize-binary-tree/

加油！：）