二叉树递归removeReftMost（）方法是如何工作的？

Question

该方法的规范声称，该方法，从根开始，将移除最左侧的节点，并修复树结构。它还指出，如果最左侧节点没有左子节点，则将右子节点（可能为null)作为左子节点附加到最左侧节点的父节点（我在代码中看不到这种情况发生的地方）。代码如下：

public BTNode removeLeftmost()
{
    if (left == null)
        return right;

    left = left.removeLeftmost();
    return this;
}

我只是不明白它是如何返回整个树和返回最左边的节点。主要是第一部分让我感到困惑，它说如果left==null返回右边的子项。如果我深入到树中（由于递归调用），返回右不就会切断树的很多部分吗？

Answer 1

下面是它正在处理的情况：

          9
         / \ 
        8   12
       / \
      5   20
       \ 
        6
         \
          7

当我们到达5时，它是最左边的节点(left==null)。我们需要移除它。因此5的右侧（即6)返回给调用方(Return right；)，调用方使6成为8的新左树(left=left.removeReftMost（）)。

          9
         / \
        8   12
       / \
      6   20
       \ 
        7

然后8返回给调用方(Return this)并分配为9的左节点(left=left.RemoveReftMost（）)。但是8已经是9的左子级，所以这不会改变任何事情。