面接問題27:ツリーのミラーリング(C++)

タイトルアドレス:https://leetcode-cn.com/problems/er-cha-shu-de-jing-xiang-lcof/
タイトルの説明
関数を完了し、ミラーを出力するツリーを入力してください.
たとえば、次のように入力します.
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]

問題を解く構想.
DFS:シーケンシャルループ実装
(1)再帰方法:二叉探索木に関わる限り,いずれも再帰的に解決することができ,問題を分析すると,二叉木のミラーリングは左右のサブツリーのノードを交換することによって変換されたものであり,我々は二叉木の先序遍歴特徴を利用して再帰的に実現し,主にサブツリーの左右のノードを交換する.
(2)スタック方法:二叉木の先序遍歴方法は二つあり、一つは再帰方法であり、もう一つは非再帰方法である.すなわちスタック実現である.ここではスタックの方法を用いて解決する.具体的な構想はルートノードをスタックに押し込み、その後スタックトップ要素の左右のサブツリーを交換し、交換後の左右のノードをスタックの左ノードと右ノードにそれぞれ押し込む.スタックが空でない場合に戻ります.
BFS:階層遍歴実装
≪キュー・メソッド|Queue Method|emdw≫:キューのメソッドを使用して、1つ1つを遍歴し、キューの最初の要素の左右のサブツリーを交換します.
プログラムソース
再帰

/**
 * 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* p = root->left;
        root->left = mirrorTree(root->right);
        root->right = mirrorTree(p);
        /*
        if(root == nullptr) return nullptr;
        swap(root->left, root->right);
        mirrorTree(root->left);
        mirrorTree(root->right);
        return root;
        */
        return root;

    }
};

スタック(非再帰)

/**
 * 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;
        stack s;
        s.push(root);
        while(!s.empty())
        {
            TreeNode* p = s.top();
            s.pop();
            if(p == nullptr) continue;
            TreeNode* q = p->left;
            p->left = p->right;
            p->right = q;
            s.push(p->left);
            s.push(p->right);
        }
        return root;
    }
};

キュー

/**
 * 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;
        queue que;
        que.push(root);
        while(!que.empty())
        {
            TreeNode* p = que.front();
            que.pop();
            if(p == nullptr) continue;
            TreeNode* q = p->left;
            p->left = p->right;
            p->right = q;
            que.push(p->left);
            que.push(p->right);            
        }
        return root;
    }
};