递归翻转二叉树

Question

public class TreeManipulator<E> {

    public TreeManipulator() {
    }

    public BinaryNode<E> flipTree(BinaryNode<E> _root) {

        BinaryNode<E> root = new BinaryNode<>(_root.getItem());

        if (_root.getLeft() != null) {
            root.setRight(new BinaryNode<>(_root.getLeft().getItem()));
            this.flipTree(_root.getLeft());
        }

        if (_root.getRight() != null) {
            root.setLeft(new BinaryNode<>(_root.getRight().getItem()));
            this.flipTree(_root.getRight());
        }

        return root;
    }
}

主要方法：

public static void main(String[] args) {
    Integer one = 1;
    Integer two = 2;
    Integer three = 3;
    Integer four = 4;
    Integer five = 5;
    Integer six = 6;
    Integer seven = 7;
    Integer eight = 8;

    //Root Node = x
    BinaryNode<Integer> x = new BinaryNode<>(one);

    //X.getLeft = y
    BinaryNode<Integer> y;

     //X.getRight = z
    BinaryNode<Integer> z;

    x.setLeft(new BinaryNode<>(two));
    x.getLeft().setLeft(new BinaryNode<>(six));
    x.getLeft().setRight(new BinaryNode<>(seven));

    x.setRight(new BinaryNode<>(three));
    x.getRight().setRight(new BinaryNode<>(four));
    x.getRight().setLeft(new BinaryNode<>(five));

    //Set root children for easier access
    z = x.getRight();
    y = x.getLeft();

    System.out.println(x.toStringPreorder());

    //Create tree manipulator
    TreeManipulator flop = new TreeManipulator();

    BinaryNode<Integer> flipped = flop.flipTree(x);

    System.out.println(flipped.toStringPreorder());       
}

如果您需要类'BinaryNode'，请询问，我会张贴它，我不想用代码交换这个问题...

输入：

null

null

我不明白为什么节点'2'和'3'返回时左值和右值为null。

Answer 1

您使用的递归错误，fliptree不会翻转您放入的对象，而是返回原始输入的翻转副本。更重要的是，您甚至没有将该输入作为根的子项，您只是将一个只包含值的节点放入，这就是为什么您只得到深度为1的树的原因。

这应该可以解决这个问题：

public BinaryNode<E> flipTree(BinaryNode<E> _root) {
    BinaryNode<E> root = new BinaryNode<>(_root.getItem());
    if (_root.getLeft() != null) {
        root.setRight(flipTree(_root.getLeft());
    }
    if (_root.getRight() != null) {
        root.setLeft(flipTree(_root.getRight());
    }
    return root;
}

如果您确实希望flipTree只是翻转树本身，而不是返回翻转后的版本，则必须执行以下操作：

public void flipTree(BinaryNode<E> root) {
    BinaryNode<E> temp = root.getLeft();
    root.setLeft(root.getRight());
    root.setRight(temp);
    if (root.getLeft() != null) {
        flipTree(root.getLeft());
    }
    if (root.getRight() != null) {
        flipTree(root.getRight());
    }
}