題目：二叉樹的鏡像

請完成一個函數(shù)，輸入一個二叉樹，該函數(shù)輸出它的鏡像。

例如輸入：

?????4
???/ ??\
??2 ????7
?/ \ ??/ \
1 ??3 6 ??9
鏡像輸出：

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

示例 1：

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

限制：

0 <= 節(jié)點個數(shù) <= 1000

---

解題：

方法一：遞歸

先定義一個遞歸出口：當遞歸到null節(jié)點時，直接返回null。接著如果當前節(jié)點不是null節(jié)點，則其左右孩子調(diào)換。最后繼續(xù)遞歸下去。解題思想是只考慮當前層孩子的調(diào)換，不用考慮下面層的事情。

/*** 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 == nullptr) return nullptr;TreeNode* temp = root->left;root->left = root->right;root->right = temp;mirrorTree(root->left);mirrorTree(root->right);return root;}
};

方法二：棧

class Solution {
public:TreeNode* mirrorTree(TreeNode* root) {stack<TreeNode*> s;s.push(root);while (!s.empty()) {TreeNode* node = s.top();s.pop();if (node == NULL) {continue;}swap(node->left, node->right);s.push(node->left); s.push(node->right);}return root;}
};

?

總結(jié)

以上是生活随笔為你收集整理的剑指offer：面试题27. 二叉树的镜像的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。