第六章二叉树——翻转二叉树

吾日三省吾身

还记得梦想吗

正在努力实现它吗

可以坚持下去吗

目录

吾日三省吾身

力扣题号：226. 翻转二叉树 - 力扣（LeetCode）

题目描述

Java解法一：层序遍历+翻转

实现思路

swapTree 方法

注意事项

代码实现

Java

C++

 

Java解法二：递归

实现思路

swap 方法

注意事项

代码实现

Java

 C++

总结

---

 

 

---

力扣题号：226. 翻转二叉树 - 力扣（LeetCode）

注：下述题目描述和示例均来自力扣

题目描述

给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。

示例 1：

输入：root = [4,2,7,1,3,6,9]
输出：[4,7,2,9,6,3,1]

示例 2：

输入：root = [2,1,3]
输出：[2,3,1]

示例 3：

输入：root = []
输出：[]

提示：

• 树中节点数目范围在 [0, 100] 内
• -100 <= Node.val <= 100

---

Java解法一：层序遍历+翻转

实现思路

        该算法通过层序遍历的方式实现二叉树的翻转。在每一层的循环中，弹出一个节点后，通过交换其左右子节点实现翻转。然后将交换后的左右子节点加入队列，继续下一轮层序遍历。

思路如下：

• 非空判断，若根节点为空，直接返回。
• 使用队列 deque 来进行层序遍历，将根节点加入队列。
• 进入循环，每次循环处理一层的节点。
  • 记录当前层的节点数量 size。
  • 在内部循环中，弹出队列中的节点，调用 swapTree 方法翻转其左右子节点。
  • 将左右孩子加入队列。
• 最终返回翻转后的二叉树的根节点。

swapTree 方法

swapTree 方法接收一个树节点作为参数，用于翻转该节点的左右子节点。

注意事项

• 代码通过队列实现了层序遍历，确保同一层的节点先被处理，实现了翻转的效果。
• swapTree 方法用于交换一个节点的左右子节点。

代码实现

Java

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode invertTree(TreeNode root) {
        // 非空判断
        if (root == null){
            return root;
        }
        // 定义一个队列用于实现层序遍历
        Deque<TreeNode> deque = new ArrayDeque<>();
        // 先将根结点加入
        deque.offer(root);
        // 层序遍历的流程
        while (!deque.isEmpty()){
            // 由于size是会改变的，所以我们先记录一下
            int size = deque.size();
            // 遍历一层
            for (int i = 0; i < size; i++) {
                // 弹出一个节点
                TreeNode node = deque.poll();
                // 交换该节点下面的子节点
                swapTree(node);
                // 层序遍历步骤，将左右孩子加入队列
                if (node.left != null){
                    deque.offer(node.left);
                }
                if (node.right != null){
                    deque.offer(node.right);
                }
            }
        }
        return root;
    }
 
    /**
     * 交换node节点的孩子
     * @param node 根节点
     */
    public void swapTree(TreeNode node){
        TreeNode temp = node.left;
        node.left = node.right;
        node.right = temp;
    }
}

C++

 

/**
 * 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 root;
        }
        std::queue<TreeNode*> que;
        que.push(root);
        while (!que.empty()) {
            int size = que.size();
            for (int i = 0; i < size; i++) {
                TreeNode* node = que.front();
                que.pop();
                swapTree(node);
                if (node->left != nullptr) {
                    que.push(node->left);
                }
                if (node->right != nullptr) {
                    que.push(node->right);
                }
            }
        }
        return root;
    }
 
 
    void swapTree(TreeNode* node) {
        TreeNode* temp = node->left;
        node->left = node->right;
        node->right = temp;
    }
};

打败了全世界的人！！！！！！！！！！！！！！！！！！

---

Java解法二：递归

实现思路

        该算法通过递归的方式实现二叉树的翻转。递归函数中，首先判断当前节点是否为空，如果为空则直接返回 null；否则，递归调用 invertTree 方法翻转左右子树，然后调用 swap 方法翻转当前节点的左右子节点。

思路如下：

• 非空判断，若根节点为空，直接返回 null。
• 递归调用 invertTree 方法分别对左右子树进行翻转。
• 调用 swap 方法翻转当前节点的左右子节点。
• 返回当前节点。

swap 方法

        swap 方法接收一个树节点作为参数，用于翻转该节点的左右子节点。

注意事项

• 代码通过递归实现了二叉树的翻转，递归函数在处理每个节点时都考虑了左右子树的翻转操作。
• swap 方法用于交换一个节点的左右子节点。

代码实现

Java

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode invertTree(TreeNode root) {
        // 如果是null返回null
        if(root == null){
            return null;
        }
        //采用后序遍历，达到交换子节点的目的
        invertTree(root.left);
        invertTree(root.right);
        swap(root);
        return root;
 
    }
    /**
        交换子节点
     */
    public void swap(TreeNode node){
        TreeNode temp = node.left;
        node.left = node.right;
        node.right = temp;
    }
}

 C++

/**
 * 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;
        }
        invertTree(root->left);
        invertTree(root->right);
        swap(root);
        return root;
    }
 
    void swap(TreeNode* node) {
        TreeNode* temp = node->left;
        node->left = node->right;
        node->right = temp;
    }
};

说实话内存开销都挺大的，但是快呀！！~~~

---

总结

        一道二叉树翻转的问题，我们提供了两种不同的解法：一种是通过层序遍历的迭代方法，另一种是通过递归方法。

        在迭代方法中，我们使用了队列来进行层序遍历，通过交换每个节点的左右子节点实现翻转。这样确保了同一层的节点先被处理，实现了翻转的效果。在递归方法中，我们采用后序遍历的方式，先递归翻转左右子树，然后再交换当前节点的左右子节点。两种方法都达到了翻转二叉树的效果，但是递归方法在代码上更为简洁。

坚持梦想，努力奋斗！！！！！