经典算法学习——交换二叉树的左右子树(二叉树的翻转)

时间:2023-01-22 10:23:42

        对于二叉树,我们必须熟练掌握它的各种操作,今天我们要来实现二叉树的翻转,也就是交换左右子树。具体思路不难,如果一个节点是叶子节点,则不做操作;如果一个节点只有左孩子或者右孩子,则进行交换,原来的孩子为空;如果一个节点既有左孩子和右孩子,则交换左右孩子。详细代码上传至 https://github.com/chenyufeng1991/ReverseLeftRightChild

核心代码如下:

// 交换左右子树void ReverseLeftRightChild(BiTNode **T)
{
// 如果是叶子节点,则递归结束
if (*T == NULL)
{
return;
}

swap((*T)->lChild, (*T)->rChild); // 直接使用swap交换函数比较方便,直接交换指针;
ReverseLeftRightChild(&((*T)->lChild));
ReverseLeftRightChild(&((*T)->rChild));
}