二叉树翻转问题详解：递归法与迭代法

二叉树翻转问题详解：递归法与迭代法

引用

CSDN

1.

https://blog.csdn.net/bufangbufang/article/details/142690657

翻转二叉树是一道经典的二叉树问题，是对二叉树进行基本操作的一个典型例子。掌握这个问题的解决方法可以为解决更复杂的二叉树相关问题打下基础。本文将分别以递归和迭代两种方法来解决这一问题，并附有完整代码示例。

一、如何理解翻转二叉树

翻转二叉树是以轴对称的方式，将二叉树的左右子树完全翻转。这里引用Leetcode的解释和例题说明：

二、方法一（递归法）

对于这道题来说，使用常规的递归算法可以很轻松地完成要求。我们定义一个递归函数invertTree，传入初始的根节点，输出翻转后的根节点。

TreeNode* invertTree(TreeNode* root) {
    return root;
}

如果传入的是nullptr，说明要么这是一个空树，要么是传入一个二叉树的叶节点的下一节点（叶节点为树的末端，因此叶节点的下一节点为空），所以我们直接返回nullptr即可，均满足上述两种情况的翻转。

TreeNode* invertTree(TreeNode* root) {
    if(root==nullptr){
        return nullptr;
    }
    return root;
}

那么，如果传入的是一个非空节点呢？我们可以定义一个节点rot，rot用来储存翻转后的左子树根节点。交换左右子树根节点。

TreeNode* invertTree(TreeNode* root) {
    if(root==nullptr){
        return nullptr;
    }
    TreeNode* rot=invertTree(root->left);
    root->left=invertTree(root->right);
    root->right=rot;
    return root;
}

完整代码如下：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if(root==nullptr){
            return nullptr;
        }
        TreeNode* rot=invertTree(root->left);
        root->left=invertTree(root->right);
        root->right=rot;
        return root;
    }
};

时间复杂度为O(n)。

三、方法二（迭代）

这个算法采用了非递归的方式，借助栈来实现二叉树的遍历和反转。通过先将节点压入栈中，然后依次取出进行处理。在遍历过程中，交换每个节点的左右子树，从而达到反转整个二叉树的目的。

首先简单介绍一下栈（stack)，栈是一种线性数据结构，栈的操作主要限定在一端进行。因此，我们可以通过出栈与入栈，实现深度优先遍历。

stack<TreeNode*> sta;
TreeNode* rot;//用于记录栈顶元素
TreeNode* tmp;//用于交换左右节点

在上述代码中可以看到，我们首先定义了一个栈sta，用来存储二叉树上的各个节点，然后我们定义了一个节点rot，用来记录栈顶元素，定义了一个节点tmp，用来实现交换两个节点。

TreeNode* invertTree(TreeNode* root) {
    if(root==nullptr){
        return nullptr;
    }  
    return root;
} 

进入invertTree函数后，首先进行判断输入的根节点是否为nullptr，如果为nullptr，说明该节点已经过了树的末端，或者这个树本身就是空的。

sta.push(root);        
while(!sta.empty()){//栈为空时，说明二叉树的全部路径，已经走完了
    rot=sta.top();//取栈顶元素
    sta.pop();//清除栈顶
    if(rot->left!=nullptr){
        sta.push(rot->left);
    }
    if(rot->right!=nullptr){
        sta.push(rot->right);
    }
    //交换左右节点
    tmp=rot->left;
    rot->left=rot->right;
    rot->right=tmp;      
}

接下来，将根节点压入栈中（先进栈后出栈，因此二叉树会一直在一个支路一直向下搜索，直到叶节点再开始回溯上一节点）。

完整代码如下：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    stack<TreeNode*> sta;
    TreeNode* rot;//用于记录栈顶元素
    TreeNode* tmp;//用于交换左右节点
    TreeNode* invertTree(TreeNode* root) {
        if(root==nullptr){
            return nullptr;
        }   
        sta.push(root);        
        while(!sta.empty()){//栈为空时，说明二叉树的全部路径，已经走完了
            rot=sta.top();//取栈顶元素
            sta.pop();//清除栈顶
            if(rot->left!=nullptr){
                sta.push(rot->left);
            }
            if(rot->right!=nullptr){
                sta.push(rot->right);
            }
            //交换左右节点
            tmp=rot->left;
            rot->left=rot->right;
            rot->right=tmp;      
        }
        return root;
    }
};

时间复杂度为O(n)。