二叉树中的非边界节点

Question

我有一个二叉树，我想打印所有非边界节点。 边界节点：所有叶子节点+从根到最左节点的路径上的所有节点+从根到最右节点的所有节点。

我使用了树结构中的额外布尔值来标识它是否为边界节点，然后遍历并打印非边界节点。有没有更好的方法，因为这种方法使用了一些额外的空间（虽然很少）。

- instance

---

“leftest” 应该是 “leftmost”，“rightest” 应该是 “rightmost”。 - Jim Mischel

Answer 1

你可能会发现有一个有用的观察结果，那就是二叉树中的非边界节点指的是（a）不是叶子节点且（b）在访问该节点的路径上，你已经向左和向右各走了一步。因此，一种选择是进行普通的树遍历，并在遍历过程中跟踪你是否已经向左或向右走过。以下是一些伪代码：

function printNonBoundaryNodesRec(root, goneLeft, goneRight) {
    if (root == null or root is a leaf) return;

    if (goneLeft and goneRight) print root.value
    printNonBoundaryNodesRec(root.left, true, goneRight);
    printNonBoundaryNodesRec(root.right, goneLeft, true);
}

function printNonBoundaryNodes(root) {
    printNonBoundaryNodesRec(root, false, false);
}

希望这可以帮到你！

- templatetypedef

---

如果你处于中间位置呢？ - Giorgi Nakeuri

@GiorgiNakeuri 对不起，我不明白你在问什么。你能解释一下吗？ - templatetypedef

他想打印非边界节点。边界是围绕树的所有节点。就像一个三角形。 - Giorgi Nakeuri