【二叉树算法题记录】226. 翻转二叉树

题目描述

题目链接
给你一棵二叉树的根节点 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==NULL) return root;
        swap(root->left, root->right);  // 首先进行左右孩子的交换
        invertTree(root->left); // 递归翻转左子树
        invertTree(root->right); // 递归翻转右子树
        return root;
    }
};

迭代法

广度优先遍历

迭代法我用的是层序遍历（广度优先遍历）。和层序遍历法的写法一样，也是用队列que来存放每一层节点，然后对该层节点进行左右孩子的翻转，并且每完成一次翻转，就将它的左右孩子节点也放进队伍后面，等待下一层的翻转。这里我们用一个int size在每一层操作的开始记录该层节点的数量。代码如下：

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        // 翻转二叉树从上往下看就是一层一层的翻转每个节点的左孩子和右孩子
        queue<TreeNode*> que;   // 用队列来存放每层的节点
        if(root!=NULL) que.push(root);
        while(!que.empty()){
            int size = que.size();    // 记录每层有多少个节点
            while(size--){
                TreeNode* node = que.front(); que.pop();
                if(node->left || node->right){
                    TreeNode* temp = node->left;
                    node->left = node->right;
                    node->right = temp;
                }
                if(node->left) que.push(node->left);
                if(node->right) que.push(node->right);
            }
        }
        return root;
    }
};

深度优先遍历

这里也给出深度优先遍历的答案：

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if (root == NULL) return root;
        stack<TreeNode*> st;
        st.push(root);
        while(!st.empty()) {
            TreeNode* node = st.top();              // 中
            st.pop();
            swap(node->left, node->right);
            if(node->right) st.push(node->right);   // 右
            if(node->left) st.push(node->left);     // 左
        }
        return root;
    }
};

实际上和广度的区别在于它用的是栈，深度优先遍历需要先进后出，我们处理完一个根节点（交换它的左右孩子），紧接着就要处理它的左子树和右子树，处理路线是纵向。而广度是处理兄弟姐妹堂表，处理路线是横向。