Recusively翻转二叉树

Question

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

以下是我的代码。当我通过它时，它似乎工作得很好，翻转每个左右节点，并递归地遍历树。 但是，看起来在返回时，它将返回一个节点，其左值和右值都为空，但原始节点（root）除外。

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' 与返回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()); 
    } 
} 

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