查找二叉树的边框

Question

我们给出了一个二叉查找树;我们需要找出它的边界。

因此，如果二进制树

  10 
    /  \ 
    50   150 
    /\  / \ 
    25 75  200 20 
/\   / /\ 
15 35  120 155 250 

应该打印出来50 25 15 35 120 155 250 20 150 10。

若二叉树是

   10 
     /  \ 
     50   150 
     /\  / 
     25 75  200 
    /\ /\  
    15 35 65 30 

应该是这样50 25 15 35 65 30 200 150 10。

这怎么办？将这个概括为二叉树会使问题变得更困难吗？

任何通过链接的帮助也将不胜感激。

P.S .:请看到模式不是从根开始，而是从左侧开始（在这种情况下）。它也可能从正确的开始，但它总是以根结束。

Answer 1

你所要求的是修改后的深度优先遍历，其中节点的值只有在1）节点是叶节点或者2）节点沿着树的“外部路径”时才被打印/返回，其中“外部路径”定义为

如果您通过跟踪来自根的所有左侧（或右侧）路径或者节点是否到达节点，节点就是“外部路径”的一部分父亲节点的右边（或左边）孩子本身是“外部路径”的一部分，但没有左（或右）儿童。

如果你知道如何编码DFS，那么这里的修改可以通过在遍历期间检查一些额外的条件来实现。

Answer 2

我不确定这个二叉树是否重要。我认为walk算法是一样的。

从左侧子树开始，并执行修改后的宽度第一步，仅当它是左侧兄弟或边缘时才打印节点。这将打印左边的兄弟姐妹，直到它碰到边缘，然后将叶子打印出来。

然后，您首先在右侧树上行走修改后的深度，然后打印右侧兄弟姐妹或树叶。这将打印所有正确的子树叶子，然后打印正确的兄弟姐妹。

Answer 3

printBorder(node *n){ 

    printLeft(n); O(log n) 
    printBottom(n); O(n) 
    printRight(n); O(log n) 
} 

printBottom(node *n) 
{ 
    int h = treeHeight(n); 
    printBottomHelper(n, 0); 
} 
printBottomHelper(n, h, max) 
{ 
    if(h == max) { 
    print n->data 
    } 
    printBottomHelper(n->left, h+1, max); 
    printBottomHelper(n->right, h+1, max); 
} 
printLeft(node *n) 
{ 
    while(n!= null){ 
    node *l = n->left; 
    l!= null ? print l->data:1 
    n =l; 
    } 
} 

Answer 4

您可以维护两个布尔值来说出要打印的内容。

调用printBorder（root，true，true）开始。编辑：不在最后打印根，但在开始时，应特殊情况下。

function printBorder(
Node node, bool printLeft, bool printRight, int height, const int MAX_HEIGHT) { 
    if (printLeft || printRight || 
    (node.left == null && node.right == null && height == MAX_HEIGHT)) { 
    print node; 
    } 
    if (node.left) printBorder(node.left, printLeft, printRight && node.right==null) 
    if (node.right) printBorder(node.right, printLeft && node.left == null, printRight) 
} 

其中MAX_HEIGHT由maxdepth（root，0）;

int maxdepth(Node node, int height) { 
    if (node == null) return height; 
    return max(maxdepth(node.left, height+1), maxdepth(node.right, height+1)) 
}