如何識別二叉搜索樹

Question

我最近遇到以下問題據說已經在技術面試被問出來的葉節點：給定一個二叉搜索樹，怎樣的序遍歷

我們是否在沒有構建樹的情況下識別葉節點？

例如：[5,3,2,4,8,7,9]

問題被留下的模糊誰貼吧和給出的模糊，我真的不知道有什麼辦法應該是爲這一個，我還沒有能夠找到在線驗證的解決方案。

該問題應該如何解決？

Answer 1

考慮您的例子：[5,3,2,4,8,7,9]

採取的第一個元素：5。

由於這是一個預先遍歷這就是根節點肯定。

現在，在序遍歷，後根ü復發的左子樹然後右子樹。

和U也知道，在BST：

nodes in left subtree < root < nodes in right subtree 

5後因此，所有串聯其中小於5元素屬於左子樹。同樣對於正確的。

還是你最終擁有這個（你不需要明確的創建樹）：

 5 
    / \ 
    [3,2,4] [8,7,9] 

現在[3,2,4]是左子樹部分序遍歷和[8,7,9]右。

爲兩個子數組執行遞歸操作，並且當您剩下大小爲1的數組時，這就是葉子。

Answer 2

我假設我們只考慮perfect BST。因爲如果它不完美，可能會有（可能）多種答案。

因此，看看preorder traversal的例子和描述，很明顯，根是先採取的，然後是「下」葉。因爲我們有一棵完美的樹，所以我們可以看到葉子總是成對的。而且我們還需要「跳過」他們的父母。

憑直覺，我建議倒退，因爲去年2個元素是葉（ '*' 表示沒有葉）：

[*,*,2,4,*,7,9] < - 的全部測試步驟如下（倒退）：

1. 需要2片葉子;
2. 跳過1個節點（他們的父母）;
3. 重複步驟[1-2];
4. 跳過1個節點（父母的父母）;
5. 完成（沒有更多元素了）。

現在演示的較大陣列上（15個元素，再次完美樹）：

[*,*,*,l,l,*,l,l,*,*,l,l,*,l,l] < - ，其中l表示葉。步驟（也向後）：

1. 1-4 from prevoius example;
2. 再前面的例子1-4;
3. 跳過1個節點（家長父母的父母）;
4. 完成（沒有更多元素）。

希望你有個想法。

至於的程序化的方法，可以發現在上面直觀的方法的重複圖案，並使用依賴於樹的高度遞歸（可easilly計算爲log2(n+1)其中n是在樹中的元素的數目，也期待wiki）但可能從數組的開始開始。僞代碼：

void getLeaves(int height) { 
    if (height == 2) {  // there is only a parent and two childs (leaves) 
     skip(1);    // skip 1 element 
     take(2);    // next two are leaves, get them 
    } 
    else { 
     skip(1);    // skip parent of parents (of parents ...) 
     getLeaves(height-1); // call on left part of array 
     getLeaves(height-1); // call on right part of array 
    } 
} 

Answer 3

void printleafnode(int*arr, int size) 
{ 
    int i = 0; 

    while(i < size) 
    { 
     if(arr[i] > arr[i+1]) 
      i= i+1; 
     else 
     { 
      if(arr[i] < arr[i+1]) 
      { 
       printf(" %d " ,arr[i]); 
       i= i+1; 
      } 
     } 
    } 
    printf(" %d ", arr[i]); 
    printf("\n"); 
} 

Answer 4

import java.util.ArrayList; 

public class PreorderArrayToTree { 

    static void printLeafNodes(ArrayList<Integer> list) { 
     if(list.size()==0)return; 
     if(list.size()==1) { 
      System.out.print(list.get(0)+" "); 
      return; 
     } 
     int parent = list.get(0); 
     ArrayList<Integer> leftChild = new ArrayList<Integer>(); 
     ArrayList<Integer> rightChild = new ArrayList<Integer>(); 
     for(int i=1; i<list.size(); i++) { 
      if(list.get(i)<parent)leftChild.add(list.get(i)); 
      if(list.get(i)>parent)rightChild.add(list.get(i)); 
     }; 
     printLeafNodes(leftChild); 
     printLeafNodes(rightChild); 
    }; 

    public static void main(String[] args) { 
     //int[] arr = {10,5,1,7,40,50}; 
     //int[] arr = {890, 325, 290, 530, 965}; 
     int[] arr = {3,2,4}; 
     ArrayList<Integer> list = new ArrayList<Integer>(); 
     for(int i=0; i<arr.length; i++)list.add(arr[i]); 
     printLeafNodes(list); 
    }; 
};