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

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

现在您想要从 leaf 转到 root ，请按照以下步骤操作。

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

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

2.一旦到达叶子节点，再次通过检查遍历回来

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

HeightCount++;

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

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