交换二叉树中深度为N的每个节点的子节点

Question

假设我们有一棵树，我们将在深度2执行一次交换：

    1                  1  
   / \                / \ 
  2   3   [s]  ->    2   3
   \   \            /   / 
    4   5          4   5  

我正在尝试编写一个函数来实现这一点：

public void swap(TreeNode node, int[] swaps, int i, int arraySize, int depth) {
        if(arraySize == 0) return;

        if(depth < swaps[i]) {
            swap(node, swaps, i+1, arraySize-1, depth+1);
        }

        if(depth == swaps[i]) {
            TreeNode temp = node.left;
            node.left = node.right;
            node.right = temp;

            swap(node.left, swaps, i+1, arraySize-1, depth+1);
            swap(node.right, swaps, i+1, arraySize-1, depth+1);
        }

    }

当我在调用方法之前和之后运行上面的do a inorder遍历树时，我得到了相同的结果：

2 4 1 3 5 

我应该得到

4 2 1 5 3

Answer 1

我相信这就是你要找的东西，

public void swap( TreeNode node, int depth, int[ ] sDepths, int sI ) {
    if( node == null || sI >= sDepths.length ) return;
    if( depth == sDepths[ sI ] ) {
        TreeNode tmp = node.left;
        node.left = node.right;
        node.right = tmp;
        sI++;
    }
    swap( node.left, depth + 1, sDepths, sI );
    swap( node.right, depth + 1, sDepths, sI );
}

解释：

首先，它验证我们没有走出树，并且有更多的交换要执行。然后，它检查当前深度是否需要交换。如果是这样，我们交换索引并将其递增到swaps数组中。然后我们对它的子代进行重复。

这要求sDepth按递增顺序排列，初始调用应类似于swap( root, 0, sDepths, 0 )