查找二叉搜索树的叶节点

我在面试中被问及在给定遍历二叉搜索树的情况下，找出叶节点而不构建原始树。我知道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

查找二叉搜索树的叶节点

回答

相关问题