反转二叉树的交替级别

Question

给定一个完美的二叉树，我需要反转交替级别：

Given tree: 
           a
        /     \
       b       c
     /  \     /  \
    d    e    f    g
   / \  / \  / \  / \
   h  i j  k l  m  n  o 

Modified tree:
           a
        /     \
       c       b
     /  \     /  \
    d    e    f    g
   / \  / \  / \  / \
  o  n m  l k  j  i  h

我正在尝试使用递归进行中序遍历并在另一个中序遍历中修改树。

public static void reverseAltLevels(TreeNode node) {
    if (node == null)
        return;
    ArrayList<TreeNode> list = new ArrayList<TreeNode>();
    storeAltNodes(node, list, 0);

    Collections.reverse(list);
    System.out.println();
    for (TreeNode n : list)
        System.out.print(n.data + " ");
    modifyTree(node, list, 0, 0);
}

public static void storeAltNodes(TreeNode node, ArrayList<TreeNode> list,
        int level) {
    if (node == null)
        return;
    storeAltNodes(node.left, list, level + 1);
    if (level % 2 != 0) {
        list.add(node);
    }
    storeAltNodes(node.right, list, level + 1);
}

public static int modifyTree(TreeNode node, ArrayList<TreeNode> list,
        int index, int level) {
    if (node == null)
        return index;
    index = modifyTree(node.left, list, index, level + 1);
    if (level % 2 != 0) {
        node.data = list.get(index).data;
        index++;
    }
    index = modifyTree(node.right, list, index, level + 1);
    return index;
}

public static void inOrder(TreeNode node) {
    if (node == null)
        return;
    inOrder(node.left);
    System.out.print(node.data + " ");
    inOrder(node.right);
}

我会将根传递给 reverseAltLevels() 函数，然后从那里调用另一个函数。

但我无法找出我的代码的确切问题，尝试在 Eclipse 中调试，对我来说似乎没问题。原中序遍历：

h d i b j e k a l f m c n g o

修改后的预期结果：

o d n c m e l a k f j b i g h

我的输出：

o d n c m e l a l f m c n g o

Answer 1

你的代码有问题

list.add(node);

现在列表对原始对象具有相同的引用

方法中

public static int modifyTree(TreeNode node, ArrayList<TreeNode> list,
            int index, int level)

您正在设置节点数据。

node.data = list.get(index).data;

导致数组list里面的数据被修改

解决您的问题。使用 Arraylist of String 来存储数据，而不是存储 Object 本身

反转二叉树的交替级别

Reverse alternate levels of a binary tree

java

algorithm

binary-tree