给定一棵二叉树(不一定是二叉搜索树)和该树中的一个节点,找到该节点的有序排名的有效算法(最好是 Java)是什么?
O(n)
算法可以通过遍历(递归或迭代)实现。有更好的吗?感谢您的任何建议。
最佳答案
想象最坏的情况:每个节点只有一个左 child ,所以整棵树变成了一个链表。
如果给定一个根,要计算等级,您需要访问叶,在本例中成本为 O(n)
。因此,O(n)
在最坏的情况下是您可以在不在节点中存储额外信息的情况下实现的最佳情况。
关于java - 查找二叉树节点有序排序的高效算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/32099264/