遍历
先序遍历
按照根节点、左节点、右节点的顺序遍历
中序遍历
按照左节点、根节点、右节点的顺序遍历
后序遍历
按照左节点、右节点、根节点的顺序遍历
举例
如图所示：
- 先序遍历: ABDCEF
- 中序遍历：BDAECF
- 后序遍历：DBEFCA
确定唯一树
- 先序和后序无法确定唯一树，因为没有中序无法确定左右子树
- 只有先序/后续 和中序才能确定唯一树
- 遍历过程，先序或后序确定根节点，中序确定左右子树
先序和中序确定唯一树
- 先序遍历: ABDCEF
- 中序遍历：BDAECF
思路：通过先序遍历确定根节点，然后通过中序确定左右子树
- 通过先序确定根节点 (先序根节点是第一个) A ，中序被分成三份 BD、A、ECF，分别是中序的左子树、根节点、右子树
- 然后根据中序把先序分成三份 A、BD、CEF ，分别是先序的根节点、左子树、右子树
- 然后确定先序BD和中序BD确定左子树的唯一
- 然后根据先序 CEF 和 中序ECF 确定 右子树的唯一
后序和中序确定唯一树
- 中序遍历：BDAECF
- 后序遍历：DBEFCA
思路：通过后序遍历确定根节点，然后通过中序确定左右子树
- 通过后序确定根节(后序根节点是最后一个)A ，中序被分成三份 BD、A、ECF，分别是中序的左子树、根节点、右子树
- 然后根据中序把后序分成三份 BD、EFC、A ，分别是后序的左子树、右子树、根节点
- 循环重复上述步骤
