给定二叉树的后序遍历和中序遍历如何确定一棵树
例如：
后序遍历为：2 1 6 9 3 5
中序遍历为：6 2 1 5 3 9
后序遍历：左子树，右子树，根节点
中序遍历：左子树，根节点，右子树
根据上面的特性，我们可以从后序遍历的最后一个数来确定这棵树的根节点，由这个数将中序遍历分割开来，分成 6 2 1 为左子树，3 9为右子树，然后后序遍历也可以由此分成 2 1 6 为左子树，9 3 为右子树，然后2 1 6，6 2 1重复上个过程，9 3，3 9也重复上个过程。
最终得到一下二叉树:
总结：其实上面那个步骤就是不断重复找当前这棵树的根节点：比如刚开始这棵树为 2 1 6 9 3 5，6 2 1 5 3 9，这棵树的根节点就是5，然后分成了2 1 6，6 2 1，也就是左子树这也是一棵树，所以他的根节点就是6，所以就是把每个节点都看成根节点把，个人的理解。重复的过程，所以可以采用递归来建树，当然如果题目换成前序和中序或者其他，我想也可以这样子做。
以上也就是我的一点心得和理解。。如果有漏洞或者错误的地方可以留言指正。
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！