算法leetcode｜剑指 Offer 27. 二叉树的镜像｜226. 翻转二叉树（rust很强）

---

---

剑指 Offer 27. 二叉树的镜像｜226. 翻转二叉树：

请完成一个函数，输入一个二叉树，该函数输出它的镜像。

例如输入：

     4
   /   \
  2     7
 / \   / \
1   3 6   9
1
2
3
4
5

镜像输出：

     4
   /   \
  7     2
 / \   / \
9   6 3   1
1
2
3
4
5

样例 1：

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

限制：

• 0 <= 节点个数 <= 1000

---

分析

• 面对这道算法题目，二当家的陷入了沉思。
• 仔细思考就会发现啊，其实就是把每个节点的左右孩子交换。
• 而树结构的遍历太适合用递归套娃大法了。

---

题解

rust

// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
//   pub val: i32,
//   pub left: Option>>,
//   pub right: Option>>,
// }
// 
// impl TreeNode {
//   #[inline]
//   pub fn new(val: i32) -> Self {
//     TreeNode {
//       val,
//       left: None,
//       right: None
//     }
//   }
// }
use std::rc::Rc;
use std::cell::RefCell;
impl Solution {
    pub fn mirror_tree(root: Option<Rc<RefCell<TreeNode>>>) -> Option<Rc<RefCell<TreeNode>>> {
        if root.is_some() {
            let mut mb = root.as_ref().unwrap().borrow_mut();
            let left = Solution::mirror_tree(mb.left.take());
            let right = Solution::mirror_tree(mb.right.take());
            mb.left = right;
            mb.right = 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
29
30
31
32

---

go

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func mirrorTree(root *TreeNode) *TreeNode {
    if root != nil {
		left := mirrorTree(root.Left)
		right := mirrorTree(root.Right)
		root.Left = right
		root.Right = left
	}
	return root
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

---

c++

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* mirrorTree(TreeNode* root) {
        if (root) {
            TreeNode *left = mirrorTree(root->left);
            TreeNode *right = mirrorTree(root->right);
            root->left = right;
            root->right = left;
        }
        return root;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

---

java

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode mirrorTree(TreeNode root) {
        if (root != null) {
            TreeNode left = mirrorTree(root.left);
            TreeNode right = mirrorTree(root.right);
            root.left = right;
            root.right = left;
        }
        return root;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

---

python

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def mirrorTree(self, root: TreeNode) -> TreeNode:
        if root:
            left = self.mirrorTree(root.left)
            right = self.mirrorTree(root.right)
            root.left = right
            root.right = left
        return root

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

---

原题传送门：https://leetcode.cn/problems/er-cha-shu-de-jing-xiang-lcof/

原题传送门：https://leetcode.cn/problems/invert-binary-tree/

---

非常感谢你阅读本文~
欢迎【点赞】【收藏】【评论】~
放弃不难，但坚持一定很酷~
希望我们大家都能每天进步一点点~
本文由 二当家的白帽子：https://le-yi.blog.csdn.net/ 博客原创~

---