查找二叉樹的邊框

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