我有一个 binary tree唯一的条件是最深层有一个节点。树中的节点具有父属性(以及左、右、数据)
是否有可能比O(N更好地确定最深层的节点是什么？ )?
如果树是 binary search tree (right->data > parent->data, left->data < parent->data) 怎么办？而不是二叉树？
我可以使用广度优先方法到达那里，该方法可以在 O(N) 内完成二叉树和二叉搜索树的工作，但我想知道是否有更好的方法。
最佳答案
没有比 O(n) 更好的方法了。
当所有节点都只有左子节点时考虑一棵树 - 您需要扫描所有节点才能到达最深的节点。
关于algorithm - 如何查找并返回二叉树的最底部(最深节点)节点？二叉搜索树？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/14999356/