查找 BST 边缘的节点

Question

BST边缘的节点是节点：同级节点中具有biggest/smallest键的节点。（不包括根节点和叶节点）

> Suppose we already have a BST like this:

                  --------5--------
                     -4--     -8---
                  -1-  -3-   -N-10-
                      -2-N-   -9--N-

So the nodes we need to find: 4,8,10 (don't use array/string)

我正在考虑使用堆栈来存储节点的键。但似乎我在弹出和比较以找到 biggest/smallest 时遇到了麻烦。那你能帮我想出更好的解决办法吗？

Answer 1

执行层序遍历（使用队列）。

每次您出队时，检查您所在的级别是否是您迄今为止记录的最小值或最大值。

在检查最小值和最大值时，确保根没有将 root.left 和 root.right 都设为 NULL

查找 BST 边缘的节点

Find nodes at the edge of a BST

c++

binary-search-tree