algorithm - 反转完美二叉树的交替级别

Question

问题陈述是:

Given a Perfect Binary Tree, reverse the alternate level nodes of the binary tree.

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 

来自 this site 的解决方案 3提供了一个特别优雅的解决方案，它在树的偶数层的节点上使用交换方法:void

preorder(struct Node *root1, struct Node* root2, int lvl)
{
    // Base cases
    if (root1 == NULL || root2==NULL)
        return;

    // Swap subtrees if level is even
    if (lvl%2 == 0)
        swap(root1->key, root2->key);

    // Recur for left and right subtrees (Note : left of root1
    // is passed and right of root2 in first call and opposite
    // in second call.
    preorder(root1->left, root2->right, lvl+1);
    preorder(root1->right, root2->left, lvl+1);
}

// This function calls preorder() for left and right children
// of root
void reverseAlternate(struct Node *root)
{
   preorder(root->left, root->right, 0);
}

但是，出于某种原因，当打印树的原始版本和修改版本的顺序遍历时，它们会产生相同的输出:

Inorder Traversal of given tree
h d i b j e k a l f m c n g o 

Inorder Traversal of modified tree
h d i b j e k a l f m c n g o 

出于某种原因，这篇文章的作者没有意识到这个问题并将其作为最终解决方案，因为它是我假设的三种方法中最短的一种。帖子中的方法 2 较长，但它会产生正确的输出。

是否存在导致两个版本的树的输出相同的解决方案错误？

Answer 1

Is there a bug with the solution that is causing the output for both versions of the tree to be the same?

算法没有错误。错误在于 main 函数从不调用 reverseAlternate()，因此它只是将同一棵树打印两次。

Add the missing call (链接中的第 76 行)，它运行良好。