二叉树递归removeLeftmost()方法是如何工作的

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.removeLeftmost())的新左树。

          9
         / 
        8   12
       / 
      6   20
        
        7

则将8返回给调用方return this，并赋值为9 (left = left.removeLeftmost())的左节点。但是8已经是9的左子元素，所以这不会改变任何东西。

Answer 2

我假设这是一个二叉搜索树，否则你就不需要修复结构，对吗?

那么它所做的就是沿着树移动，直到左边没有更多的分支，也就是说，只相对于左边，你已经到达了一个叶子。

if (left !=null){ left = left.removeLeftmost(); }

此时，它将子树右侧的分支移植到父树左侧树所在的位置(再次通过left = left.removeLeftmost();)，然后它将返回之前位于同一位置的分支，一直返回到树的根。