题目描述
输入一个二叉树，将它变换为它的镜像。
数据范围
树中节点数量 [0,100]。
样例
输入树： 8 / \ 6 10 / \ / \ 5 7 9 11 [8,6,10,5,7,9,11,null,null,null,null,null,null,null,null] 输出树： 8 / \ 10 6 / \ / \ 11 9 7 5 [8,10,6,11,9,7,5,null,null,null,null,null,null,null,null]
方法一：二叉树，递归 O(n)
这道题直接递归即可，每次递归都交换左右指针。我们拿题目的样例来举例，看看具体的效果是什么：
第一步： 交换根结点的左右两个指针。
第二步： 递归到根结点的左右两个结点执行交换操作，先递归左结点，并交换其左右指针。
第三步： 由于已经到了叶子结点，回溯到根结点继续递归其右结点，并交换其左右指针。
/** * 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: void mirror(TreeNode* root) { if (!root) return; swap(root->left, root->right); mirror(root->left); mirror(root->right); } };
欢迎大家在评论区交流~
