如何删除二叉树的叶子？

Question

我正在尝试删除所有的叶子.我知道叶子没有孩子,这就是我到目前为止所拥有的.

 public void removeLeaves(BinaryTree n){  

    if (n.left == null && n.right == null){

        n = null;

    }

    if (n.left != null)

        removeLeaves(n.left);

    if (n.right != null)

        removeLeaves(n.right);

}

Answer 1

n = null;不会帮助你,因为n它只是你函数的局部变量.相反,您需要设置n.left = null;或n.right = null;在父级上.

我不会给你一个完整的解决方案,因为这闻起来很像功课,但你可以,例如,返回值添加到您的函数,表示有问题的节点是否为叶与否,并采取适当的行动父母(致电后removeLeaves).

Answer 2

如果你这样打破它会容易得多:

public void removeLeaves(BinaryTree n){
  if (n.left != null) {
    if (n.left.isLeaf()) {
      n.removeLeftChild();
    } else {
      removeLeaves(n.left);
    }
  }
  // repeat for right child
  // ...
}

isLeaf,removeLeftChild而removeRightChild应该是微不足道的实施.