剑指offer27树的镜像

请完成一个函数&＃xff0c;输入一个二叉树&＃xff0c;该函数输出它的镜像。输入&＃xff1a;4/ \2 7/ \ / \
1 3 6 9
输出&＃xff1a;4/ \7 2/ \ / \
9 6 3 1


思路一&＃xff1a;递归

递归返回条件&＃xff1a;如果root为空&＃xff0c;返回空

交换左右子树
把root的左子树放到mirrorTree中镜像一下
把root的右子树放到mirrorTree中镜像一下

返回根节点root

先交换还是先镜像都可以&＃xff0c;对顺序没有要求

TreeNode* mirrorTree(TreeNode* root) {if(root &＃61;&＃61; NULL) return NULL;swap(root->left,root->right);if(root->left) mirrorTree(root->left);if(root->right) mirrorTree(root->right);return root;
}


思路二&＃xff1a;迭代

不难发现&＃xff0c;递归求解的本质其实就是前序遍历
因此可以用栈解决

TreeNode* mirrorTree(TreeNode* root) {if(root &＃61;&＃61; NULL) return NULL;stack<TreeNode*> stk;stk.push(root);while(!stk.empty()) {TreeNode* node &＃61; stk.top();stk.pop();swap(node->left,node->right);if(node->right) stk.push(node->right);if(node->left) stk.push(node->left);}return root;}