1分钟部署网站📞AI智能客服,大模型训练自有数据,简单好用,有效降低客服成本 广告
二叉树: ![](https://pic4.zhimg.com/80/v2-0fcc909a2787cd92c1315481748d2b57_720w.jpg) 前序遍历A-B-D-F-G-H-I-E-C 中序遍历F-D-H-G-I-B-E-A-C 后序遍历F-H-I-G-D-E-B-C-A **前序(根左右),中序(左根右),后序(左右根)** 例题1: 已知某二叉树的前序遍历为A-B-D-F-G-H-I-E-C,中序遍历为F-D-H-G-I-B-E-A-C,请还原这颗二叉树。 解题思路: 从前序遍历中,我们确定了根结点为A,在从中序遍历中得出 F-D-H-G-I-B-E在根结点的左边,C在根结点的右边,那么我们就可以构建我们的二叉树的雏形。 ![](https://pic1.zhimg.com/80/v2-117aade0ca15b451e9a542b6852631f0_720w.png) 那么剩下的前序遍历为B-D-F-G-H-I-E,中序遍历为F-D-H-G-I-B-E, B就是我们新的“根结点”,从中序遍历中得出F-D-H-G-I在B的左边,E在B的右边,继续构建 ![](https://pic1.zhimg.com/80/v2-6b585a528009e0978254153dbb43ef70_720w.jpg) 那么剩下的前序遍历为D-F-G-H-I,中序遍历为F-D-H-G-I,D就是我们新的“根结点”,从中序遍历中得出F在D的左边,H-G-I在D的右边,继续构建 ![](https://pic4.zhimg.com/80/v2-99457807b6951cd6a63a46c7a48ef0bb_720w.jpg) 那么剩下的前序遍历为G-H-I,中序遍历为H-G-I,G就是我们新的“根结点”,从中序遍历中得出H在G的左边,I在G的右边,继续构建 ![](https://pic1.zhimg.com/80/v2-85c57eed2a58fd0bddcfd878ed2f13f4_720w.jpg) 例题2: 已知某二叉树的中序遍历为F-D-H-G-I-B-E-A-C,后序遍历为F-H-I-G-D-E-B-C-A,请还原这颗二叉树。 解题思路: 从后序遍历中,我们确定了根结点为A,在从中序遍历中得出 F-D-H-G-I-B-E 在根结点的左边,C在根结点的右边,那么我们就可以构建我们的二叉树的雏形。之后就是新根节点B,FDHGI在根左,E在根右。在之后就是新根D,F根左,HGI根右,然后就差不多了。 和前序和中序还原二叉树一样,我们同理可以通过中序和后序还原二叉树。 ![](https://pic2.zhimg.com/80/v2-d7e98be21ee70faadaaf73a3c697e6c9_720w.jpg) **光有前序遍历和后序遍历是无法还原二叉树的。**