东方市住房和城乡建设局网站,有什么学做木工的网站吗,大型 视频网站开发,免费手机网页剑指 Offer 27. 二叉树的镜像
难度#xff1a;easy\color{Green}{easy}easy 题目描述
请完成一个函数#xff0c;输入一个二叉树#xff0c;该函数输出它的镜像。
例如输入#xff1a;
镜像输出#xff1a;
示例 1#xff1a;
输入#xff1a;root [4,2,7,1,3,…剑指 Offer 27. 二叉树的镜像
难度easy\color{Green}{easy}easy 题目描述
请完成一个函数输入一个二叉树该函数输出它的镜像。
例如输入
镜像输出
示例 1
输入root [4,2,7,1,3,6,9]
输出[4,7,2,9,6,3,1]限制
0节点个数10000 节点个数 10000节点个数1000
注意本题与主站 226 题相同https://leetcode-cn.com/problems/invert-binary-tree/ 算法
(递归) 根据二叉树镜像的定义考虑递归遍历dfs二叉树交换每个节点的 左 / 右子节点即可生成二叉树的镜像。
递归解析
终止条件 当节点 root 为空时即越过叶节点则返回 null
递推工作
开启递归 左子节点 mirrorTree(root.left) 并将返回值作为 root 的 左子节点 。开启递归 左子节点 mirrorTree(root.right) 并将返回值作为 root 的 右子节点 。
返回值 返回当前节点 root
复杂度分析 时间复杂度O(n)O(n)O(n)其中 nnn 是链表的长度。需要遍历链表一次 空间复杂度 : O(1)O(1)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;}
};
