[water_basic]二叉树的镜像(栈实现前序遍历)

题目描述

操作给定的二叉树，将其变换为源二叉树的镜像。

思路：

1.简单递归版（后序）

#include <iostream>
#include <vector>
using namespace std;

struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};

class Solution {
public:
    void Mirror(TreeNode *pRoot) {
        post(pRoot);
    }
    void post(TreeNode *t){
        if(t==NULL)
            return ;
        post(t->left);
        post(t->right);
        TreeNode *tempt = t->left;
        t->left = t->right;
        t->right = tempt;
    }
};

2.栈手动先序遍历（中序只需微调）:
前/中序遍历：入栈指左，出栈指右，左父右祖(出)。

class Solution_vstack {
public:
    void swapChild(TreeNode *t){
        TreeNode *tempt = t->left;
        t->left = t->right;
        t->right = tempt;
    }
    void Mirror(TreeNode *pRoot) {
       vector<TreeNode *> v;
       TreeNode *t = pRoot;
       while(!(v.empty()&&t==NULL)){
           while(t != NULL){
               v.push_back(t);
               swapChild(t);
               t = t->left;
           }
           t = v[v.size()-1];
           v.pop_back();
           t = t->right;
       }
    }
};