Recusively Flipping Binary Tree

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», пожалуйста, спросите, Ill пост это, я не хочу, чтобы поменять вопрос с кодом. ..

вход:

• Входной = [ 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()); 
    } 
} 

Кстати, я знаю, что вы сказали, что не ищете код, но для подсказок, но ваш исходный код был уже настолько близок, что трудно дать подсказку, не прибегая к немедленному исправлению кода.