java - 递归翻转二叉树

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”类，请询问，我会发布它，我不想用代码交换问题...

输入:

• 输入 = [ 1267354 ]

预期输出:

• 原始树 = [ 1267354 ]

• 翻转后 = [ 1345276 ]

我的输出:

• 翻转后 - '[ 132 ]'

我无法弄清楚为什么节点“2”和“3”返回的左值和右值均为空。

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());
    }
}

顺便说一句，我知道你说过你不是在寻找代码而是在寻找提示，但你的原始代码已经非常接近，以至于在不立即修复代码的情况下很难给出提示。