algorithm - 二叉树中的非边界节点

Question

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

我已经使用树结构中的额外 bool 值来识别它是否是边界节点，然后进行遍历并在不是边界节点时打印。有人能想出更好的方法吗，因为它使用了一些额外的空间(虽然很少)。

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);
}

希望这对您有所帮助!