剣指offer-二叉木ミラー
9191 ワード
テーマの説明は1つの関数を完成して、1つの二叉木を入力して、この関数はそのミラーを出力します.例えば入力: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<=ノード個数<=1000
解法一:再帰(C++)
解法二:スタックシミュレーション(C++)
解法三:キューシミュレーション(C++)
解法一:再帰(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 == NULL) {
return NULL;
}
mirrorTree(root->left);
mirrorTree(root->right);
swap(root->left, root->right);
return root;
}
};
解法二:スタックシミュレーション(C++)
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;
}
};
解法三:キューシミュレーション(C++)
class Solution {
public:
TreeNode* mirrorTree(TreeNode* root) {
queue<TreeNode*> q;
q.push(root);
while(!q.empty())
{
TreeNode* node = q.front();
q.pop();
if(node==NULL) continue;
swap(node->left, node->right);
q.push(node->left);
q.push(node->right);
}
return root;
}
};