如何确定二叉树的根节点？附三类遍历序列求解问题

一、不同遍历序列下根节点的判定规则 #

• 前序遍历：遵循根节点 → 左子树 → 右子树的遍历顺序，因此序列的第一个元素必然是根节点。
• 后序遍历：遵循左子树 → 右子树 → 根节点的遍历顺序，因此序列的最后一个元素必然是根节点。
• 中序遍历：遵循左子树 → 根节点 → 右子树的遍历顺序，仅依靠单独的中序序列无法唯一确定根节点——不同结构的二叉树可能拥有完全相同的中序遍历结果，必须结合前序或后序序列才能精准定位根节点。

二、给定序列的根节点查找 #

• a) 后序遍历序列FCBDG：按照后序规则，最后一个元素为根节点，即 G。
• b) 前序遍历序列IBCDFEN：按照前序规则，第一个元素为根节点，即 I。
• c) 中序遍历序列CBIDFGE：仅提供中序序列的情况下，无法唯一确定根节点，需要补充前序或后序遍历序列才能进一步判断。

内容的提问来源于stack exchange，提问作者Juniors