网站的建设费 账务处理百度知道首页登录

剑指 Offer 27. 二叉树的镜像

难度：$easy$

---

题目描述

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

例如输入：

镜像输出：

示例 1：

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

限制：

$0<=节点个数<=1000$

注意：本题与主站 226 题相同：https://leetcode-cn.com/problems/invert-binary-tree/

---

算法

(递归)

根据二叉树镜像的定义，考虑递归遍历（dfs）二叉树，交换每个节点的 左 / 右子节点，即可生成二叉树的镜像。

递归解析：

终止条件： 当节点 root 为空时（即越过叶节点），则返回 null ；

递推工作：

• 开启递归 左子节点 mirrorTree(root.left) ，并将返回值作为 root 的 左子节点 。
• 开启递归 左子节点 mirrorTree(root.right) ，并将返回值作为 root 的 右子节点 。

返回值： 返回当前节点 root ；

复杂度分析

• 时间复杂度：$O(n)$，其中 $n$ 是链表的长度。需要遍历链表一次

• 空间复杂度 : $O(1)$

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) return NULL;auto left = mirrorTree(root->left);auto right = mirrorTree(root->right);root->left = right;root->right = left;return root;}
};