二叉树最左、最右节点判定及不同遍历规则适用问题

结论 #

这棵二叉树的最左节点为4，最右节点为6。

遍历规则的适用范围说明 #

你查到的几条规则中，只有中序遍历的首项对应最左节点、尾项对应最右节点是适用于所有二叉树的通用规则，剩余几条都仅能在完美二叉树中生效：

• 后序遍历首项对应最左节点：仅完美二叉树可用。普通二叉树中如果最左节点没有左子节点、但有右子节点，后序遍历会先访问这个右子节点，导致后序首项不是最左节点，你给出的示例中7就是最左节点4的右子节点，所以后序首项为7。
• 前序遍历尾项对应最右节点、层序遍历尾项对应最右节点：仅完美二叉树可用。普通二叉树中最右节点可能有左子节点，这个左子节点会是深度更大的节点，会成为前序、层序遍历靠后的项，但它不是整棵树的最右节点，你给出的示例中9就是最右节点6的左子节点，所以前序、层序的尾项都是9而非6。

对应遍历结果验证 #

你给出的遍历结果完全符合上述逻辑：

// 中序遍历符合通用规则，首项4为最左节点，尾项6为最右节点
const inOrder    = [4, 7, 2, 1, 8, 5, 3, 9, 6];
// 前序遍历尾项为9，是最右节点的左后代，不适用普通二叉树
const preOrder   = [1, 2, 4, 7, 3, 5, 8, 6, 9];
// 后序遍历首项为7，是最左节点的右后代，不适用普通二叉树
const postOrder  = [7, 4, 2, 8, 5, 9, 6, 3, 1];
// 层序遍历尾项为9，是深度最大的节点但不是最右节点，不适用普通二叉树
const levelOrder = [1, 2, 3, 4, 5, 6, 7, 8, 9];

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