算法力扣刷题记录 四十【226.翻转二叉树】

前言

继续二叉树其余操作：
记录 四十【226.翻转二叉树】

---

一、题目阅读

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

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

---

二、尝试实现

思路

如何翻转：每个节点的左右孩子交换。确定用递归实现。
（1）确定参数和返回值：

• 参数：根节点（整个树/某个子树）
• 返回值void。直接用指针修改对象。无需返回值。

（2）确定终止条件：

• 遇到叶子节点：没有左右孩子，可以return。
• 遇到空节点：直接return。
• if(!cur || cur->left == nullptr && cur->right == nullptr) return;

（3）逻辑：先深入到叶子节点，再交换操作。

• 先走左边：递归cur->left。
• 再走右边：递归cur->right。
• 交换操作：如果左右孩子都有，互相交换；如果只有一边，换到另一边；

代码实现

/**
 * 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:
    void invertchild(TreeNode* cur){
        if(!cur || cur->left == nullptr && cur->right == nullptr){ //遇到空或叶子节点返回
            return;
        }
        invertchild(cur->left);
        invertchild(cur->right);

        //交换
        if(cur->left && cur->right){
            TreeNode* temp = cur->left;
            cur->left = cur->right;
            cur->right = temp;
        }else if(cur->left && !cur->right ){
            cur->right = cur->left;
            cur->left = nullptr;
        }else if(cur->right && !cur->left){
            cur->left = cur->right;
            cur->right = nullptr;
        }

    }
    TreeNode* invertTree(TreeNode* root) {
        invertchild(root);
        return root;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

---

参考思路

参考代码链接

学习内容

参考思路

中心思想：交换每个节点的左右孩子。所以不管是哪种遍历，得遍历到每一个节点。

1. 法一——递归法：使用前序、后序遍历；交换操作直接用swap。结合二、的代码实现改变下。二、中的遍历方式——后序遍历。参考代码对应前序遍历。

/**
 * 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;
        invertTree(root->left);
        invertTree(root->right);
        swap(root->left,root->right);
        return root;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

2. 法二——迭代法。用前序的迭代。

/**
 * 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) return root;
        stack<TreeNode*> st;
        st.push(root);
        while(!st.empty()){
            TreeNode* cur = st.top();//中
            st.pop();
            swap(cur->left,cur->right);
            
            if(cur->right) st.push(cur->right);//先放右。交换之后的右是原来的左。下一轮先处理原来的右。
            if(cur->left) st.push(cur->left);//后放左。交换之后的左是原来的右。下一轮先处理这个，这是原来的右。
        }
        return root;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

• 法三——统一迭代方式。
• 法四——层序遍历。
  对比参考代码：参考：先swap，再push；

/**
 * 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) return root;
        queue<TreeNode*> que;
        que.push(root);
        while(!que.empty()){
            int size = que.size();
            while(size--){
                TreeNode* cur = que.front();
                que.pop();
                if(cur->left) que.push(cur->left); //下一轮先处理原先的左子树。此时是交换之后的右子树。
                if(cur->right) que.push(cur->right);
                swap(cur->left,cur->right);
            }
        }
        return root;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

---

总结

翻转二叉树：遍历到每一个节点，交换左右孩子。

基础还是遍历方式。选择一种遍历方式即可。

（欢迎指正，转载标明出处）