我最近遇到了以下技术面试问题:
给定二叉搜索树的前序遍历,如何在不构建该树的情况下识别出叶节点?
例如:[5,3,2,4,8,7,9]
由于发布这个问题的人留下了许多不明确的地方,因此我不确定应该采用何种方法解决这个问题,而且我也没有能够在网上找到经过验证的解决方案。
如何解决这个问题?
[5,3,2,4,8,7,9]
取第一个元素:5
。 nodes in left subtree < root < nodes in right subtree
5
/ \
[3,2,4] [8,7,9]
现在[3,2,4]
是左子树部分的前序遍历,而[8,7,9]
是右子树的前序遍历。
对于两个子数组进行递归处理,当剩下只有一个元素时,那就是叶子节点了。
[*,*,2,4,*,7,9]
<-- 整个过程如下(反向进行):
[*,*,*,l,l,*,l,l,*,*,l,l,*,l,l]
<-- 这里的 l
表示叶子节点。步骤(也可以反向):
希望你有了一个想法。
至于编程方法,你可以在上述直观方法中发现一个重复的模式,并根据树的高度使用递归(可以通过计算树中元素数量的对数加 1 轻松计算,也可以查看 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
}
}
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);
};
};
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");
}