java - 如何在不使用父引用节点的情况下在二叉树中找到光标的父节点

Question

我正在尝试将光标移动到二叉树中的父节点。我想递归地执行此操作，而不使用保留节点来跟踪父级。我认为我的基本/停止情况是正确的，但我相信最后两个 if 语句是错误的。我不确定该怎么做。任何建议都会有所帮助。谢谢。

   public void cursorToParent()
{
    TreeNode parent = root;
    if(cursor == root )
        return;
    if(parent.getLeft().equals(cursor) || parent.getRight().equals(cursor) )
        cursor = parent;
    else
        if(parent.getLeft()!=null)
        {
            parent = parent.getLeft();
            cursorToParent();
        }
        if(parent.getLeft()!=null)
        {
            parent = parent.getLeft();
            cursorToParent();
        }

}

Answer 1

需要将当前处理节点传递给该方法。因此必须有一个方法 cursorToParentImpl() ，它将从前一个方法中使用 root 调用:

public boolean cursorToParentImpl(TreeNode current)
{
    if(cursor == current )
        return false;
    if(current.getLeft () == cursor || current.getRight() == cursor) {
        cursor = current;
        return true;
    }
    else { // note the missing parenthesis too
        if(current.getLeft()!=null) {
            if (cursorToParentImpl(current.getLeft()))
                return true;
        }
        if(current.getRight()!=null) {
            if (cursorToParentImpl(current.getRight()))
                return true;
        }
    }
    return false;
}

并称其为:

public void cursorToParent()
{
    if (cursor == root)
        return;
    cursorToParentImpl(root);
}

此外，您可以避免调用 equals() 并仅使用 == 运算符，因为这里它应该比较对节点的引用。