查找二叉搜索樹的葉節點

我在面試中被問及在給定遍歷二叉搜索樹的情況下，找出葉節點而不構建原始樹。我知道binary search tree必須滿足的財產，但我找不到任何關係到如何利用這個屬性來完成。只有我可以識別的是preorder traversal中的first node將始終是根。谷歌搜索也沒有產生這個問題的任何結果。我不希望代碼只是一個簡單的提示開始就足夠了。查找二叉搜索樹的葉節點

編輯：嘗試了很多後，我得到了這個解決方案：

#include<iostream> 
#include<vector> 
#include<string> 
using namespace std; 

void fl(vector<int> &v, int lo, int hi){ 
    if (lo>hi) return; 
    if (lo == hi) { cout<<"leaf ^^^^^^^ "<< v[hi]<<"\n"; return; } 
    int root = v[lo]; 
    int i; 
    for(i = lo+1 ; i <= hi ; i++) if (v[i] > root) break; 
    fl(v, lo+1, i -1); 
    fl(v, i , hi); 
} 

int main(){ 
vector<int> v1 = {8, 3, 1, 6, 4, 7, 10, 14, 13}; 
vector<int> v2 = {27, 14, 10, 19, 35, 31, 42}; 
vector<int> v3 = {9,8,7,6,5,4,3,2,1}; 
fl(v3,0,v3.size()-1); 
return 0; 
}

比變量名其他改善將是非常有幫助的任何建議

來源

2017-02-16 anekix

這個程序應該從一個序打印葉節點BST。該計劃是相當自我解釋。

public static void findLeafs(int[] arr) { 
     if (arr == null || arr.length == 0) 
      return; 

     Stack<Integer> stack = new Stack<>(); 
     for(int n = 1, c = 0; n < arr.length; n++, c++) { 
      if (arr[c] > arr[n]) { 
       stack.push(arr[c]); 
      } else { 
       boolean found = false; 
       while(!stack.isEmpty()) { 

        if (arr[n] > stack.peek()) { 
         stack.pop(); 
         found = true; 
        } else 
         break;  
       } 
       if (found) 
        System.out.println(arr[c]); 
      } 

     } 
     System.out.println(arr[arr.length-1]); 
    }

來源

2017-02-18 05:53:04

一個簡單的解釋邏輯將是非常有益的。只是它做了什麼 – anekix

def getLeafNodes(data): 
    if data: 
     root=data[0] 
     leafNodes=[] 
     process(data[1:],root,leafNodes) 
     return leafNodes 

def process(data,root,leafNodes): 
    if data: 
     left=[] 
     right=[] 
     for i in range(len(data)): 
      if data[i]<root: 
       left.append(data[i]) 
      if data[i]>root: 
       right.append(data[i]) 

     if len(left)==0 and len(right)==0: 
      leafNodes.append(root) 
      return 
     if len(left)>0: 
      process(left[1:],left[0],leafNodes) 
     if len(right)>0: 
      process(right[1:],right[0],leafNodes) 
    else: 
     leafNodes.append(root) 

#--Run-- 
print getLeafNodes([890,325,290,530,965])

來源

2017-06-09 06:00:34 TangledMaximus

查找二叉搜索樹的葉節點

回答

相關問題