algorithm - 修改后的二叉树的有序遍历

Question

这是在一次采访中被问到的，但我搞砸了。我们得到了一棵二叉树，但是，它被修改为它的 child 永远不会为空，如果一个非叶节点没有 child ，那么它的右/左 child 指向节点本身。而对于叶节点，它们指向下一个左节点和右节点。对于最左边和最右边的节点，它将指向它自己和上一个/下一个元素。

示例:

        1
     /     \
    2       3
  /  \     / \
(4 =  5 = 6 = 7)

这里 4.left = 4 , 4.right = 5 , 5.left = 4 和 5.right = 6 等等。

我们需要对这棵树进行中序遍历。

我提出了确定节点是否为叶节点的条件(退出条件):

 if(root.right==root || root.left == root || root.left.right == root || root.right.left == root)

但无法正确组合这些。我们还需要处理甚至根满足条件 root.left = root || 的倾斜树。 root.right = right ，因此我们将直接退出递归，甚至无需遍历整棵树。

请帮帮我。我无法为递归提出适当的条件检查。

我们只需要对这棵树进行有序遍历即可。输出:4 2 5 1 6 3 7

Answer 1

下面的算法应该做的:

visit(vertex v) {
    if (v.left != v && v.left.right != v) visit(v.left)
    print v
    if (v.right != v && v.right.left != v) visit(v.right)
}

我认为您的问题是您试图一次做太多事情。与其检测顶点是否是叶子，不如先检测它是否有左 child ，然后再检测它是否有右 child 就足够了。