java - 在 BST 中查找节点到根的距离

Question

我想在链表二进制搜索树中找到给定节点到根的距离。我有下面的代码来计算树的高度（root.getHeightN()），从根到叶，但我现在需要的是从叶到根。

public int getHeightN(){
                int l, r;

                if(this.left == null){
                    l = 0;
                }else{
                    l = this.left.getHeightN();
                }

                if(this.right == null){
                    r = 0;
                }else{
                    r = this.right.getHeightN();
                }

                if(r > l){
                    return 1+r;
                }else{
                    return 1+l;
                }
            }

这是节点类：

protected class Node
{
    Key key ;
    Val val ;
    Node left , right ;
    Node ( Key key , Val val )
    {
        this.key = key ;
        this.val = val ;
    }

Answer 1

您需要在每个节点中有额外的字段来存储父信息。如果只想打印从node(N)到根节点的路径，可以不带任何字段，否则需要在每个节点中存储父信息。您将不得不从根遍历到节点 (N)，然后开始使用节点中有关父节点的信息向上移动。由于您正在向下遍历到达节点，因此计算其他方向的高度没有多大用处:)

Answer 2

我可以在这里提出如何继续前进的概念。

由于现在您想从 Leaf 转到 root ，请按照以下步骤操作。

1.遍历树直到叶子节点（不计算高度）

只需检查if(ptr->next != null) ptr++;

2.一旦你到达叶节点，再次通过检查回溯

if(ptr(Parent)) //如果父级存在则返回 TRUE 否则 FALSE

高度计数++；

3.这样你会到达根节点，然后停止遍历。

4.HeightCount的值是树的高度（即 BST 中节点到根的距离）。