如何识别二叉搜索树的叶节点

Question

我最近遇到了以下技术面试问题：

给定二叉搜索树的前序遍历，如何在不构建该树的情况下识别出叶节点？

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

由于发布这个问题的人留下了许多不明确的地方，因此我不确定应该采用何种方法解决这个问题，而且我也没有能够在网上找到经过验证的解决方案。

如何解决这个问题？

- loremIpsum1771

Answer 1

考虑以下例子：[5,3,2,4,8,7,9] 取第一个元素：5。

由于这是一个先序遍历，所以它肯定是根节点。

现在，在先序遍历中，对于左子树和右子树进行递归。

此外，您还知道在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]是右子树的前序遍历。

对于两个子数组进行递归处理，当剩下只有一个元素时，那就是叶子节点了。

- pseudo_teetotaler

---

这种方法似乎是正确的，尽管它基于另一个答案中建议的树是完美和完整的假设。 - loremIpsum1771

我认为树并不需要完美或完整。例如：对于[2,3]，这不是一棵完美的树，但算法可以处理它。 - pseudo_teetotaler

Answer 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 步骤;
2. 再次执行与之前相同的 1-4 步骤;
3. 跳过一个节点（父节点的父节点的父节点）;
4. 完成（没有更多元素）。

希望你有了一个想法。

至于编程方法，你可以在上述直观方法中发现一个重复的模式，并根据树的高度使用递归（可以通过计算树中元素数量的对数加 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
    }
}

- Yuriy Ivaskevych

---

我认为你需要根据另一个答案中的建议利用二叉搜索树（BST）的特性。 - loremIpsum1771

它不必是一个“完美”的二叉搜索树，仍然只有一个答案。因为对于一个二叉搜索树只有一种前序遍历方式。所以我们不能倒退并找到叶节点。考虑前序遍历899、999、1099，只有一个叶节点。 - Deep

Answer 3

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

- Amber Singh

---

你应该添加解释说明你的代码如何解决问题。 - moggi

Answer 4

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

- Prasad

---

我已经格式化了你的代码块，但它仍然缺乏任何解释，这使得它成为一个不太有用的答案。 - user6655984

虽然答案总是受欢迎的，但这个问题已经在6个月前被提出，并且已经有了一个被接受的解决方案。请尽量避免通过回答来使问题重新浮现到顶部，除非该问题尚未被标记为已解决，或者您找到了一个新的和改进的解决方案。还要记得提供一些关于您的代码的上下文来帮助解释它。查看撰写优秀答案的文档，获取一些有关如何使您的答案有价值的提示 :) - Obsidian Age

在二叉搜索树中，给定一个先序遍历的数组，找到所有叶节点。 输入： {10, 5, 1, 7, 40, 50} 输出： 1 7 50 - EmptyData