算法1:利用上述遍历二叉树的方法(比如说前序遍历),把访问操作修改为交换左右节点的逻辑:
static void PreOrder(ref BinNode root)
{
if (root == null)
return;
//visit current node
BinNode temp = root.Left;
root.Left = root.Right;
root.Right = temp;
PreOrder(ref root.Left);
PreOrder(ref root.Right);
}
算法2:使用循环也可以完成相同的功能。
static void PreOrder2(ref BinNode root)
{
if (root == null)
return;
Stack stack = new Stack();
stack.Push(root);
while (stack.Count > 0)
{
//visit current node
BinNode temp = root.Left;
root.Left = root.Right;
root.Right = temp;
if (root.Left != null)
stack.Push(root.Left);
if (root.Right != null)
stack.Push(root.Right);
}
}