求助一道BST题

BST树节点有高度、值、三个指针（两个孩子节点和父节点），在logn时间复杂度下找到中位数值。
万分感谢！！

david_smith 发表于 2020-4-23 10:56
BST 你要把他换成balance BST， 每个节点加一个变量来记录这个节点的右子树及右子树的子孙中共有多少节点， ...

楼主的题目没有说可以换成balanced BST，我的理解是，如果要把不平衡的树转换成平衡树那就没意义了，因为需要in order traversal，这个本身就是O(n)的操作了。另外我想跟楼主确认一下，每个节点里面的高度指的是当前节点和root之间的差还是到该节点subtree最底层的高度差？

neweggg 发表于 2020-4-23 11:08
楼主的题目没有说可以换成balanced BST，我的理解是，如果要把不平衡的树转换成平衡树那就没意义了，因为 ...

height 指的是每个节点到叶子节点的最长路径。
谢谢关注！是不是可以做出来？
求大神点拨！

mylarryshell 发表于 2020-4-23 06:19
这个题缺条件。如果bst是单枝树，比如所有节点都在左子树上，那么不会有logn的算法找中位数。
另外n代表的 ...

n应该是代表节点数。更正下：是在O(height)时间复杂度完成。
谢谢回复！

对于树的形状有要求么？比如是balanced还是skewed

这个题缺条件。如果bst是单枝树，比如所有节点都在左子树上，那么不会有logn的算法找中位数。
另外n代表的是什么？节点个数还是树里节点的最大值？

neweggg 发表于 2020-4-23 03:28
对于树的形状有要求么？比如是balanced还是skewed

没有特别要求，只是一个BST。
谢谢回复！

BST 你要把他换成balance BST， 每个节点加一个变量来记录这个节点的右子树及右子树的子孙中共有多少节点，这样你就可以在Log N的时间内找到中位数了

我觉得这题没法做，考虑满二叉树的情况，除了把整棵树遍历一遍，不然没法说明根节点的左右子树大小相等。

是否提前知道节点总个数？