递归翻转二叉树

Question

我有这个家庭作业，我需要翻转二叉树。我不是在寻找代码或任何东西，只是提示为什么我的方法不起作用。

下面是我的代码。当我单步执行它时，它似乎工作得很好，翻转每个左右节点，并递归地在树中移动。然而，似乎在它的 return 上，它是 returning 一个左值和右值都为空的节点，除了原始节点（根）。

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

如果你需要class 'BinaryNode'，请问，我会post它，我不想用代码交换问题...

输入：

输入 = [ 1267354 ]

预期输出：

原始树 = [ 1267354 ]
翻转后 = [ 1345276 ]

我的输出：

翻转后 - '[132]'

我无法弄清楚为什么节点“2”和“3”return具有空左右值。

Answer 1

你用错了递归，flipTree 不会翻转你放入其中的对象，它returns 是原始输入的翻转副本。更重要的是，您甚至不将该输入作为根的子节点，您只需放置一个仅包含值的节点，这就是为什么您只得到一棵深度为 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());
    }
}

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

递归翻转二叉树

Recursively flipping a binary tree

java

recursion

binary-tree