翻转二叉树

原题：

翻转一棵二叉树。

示例：

输入：

  1.      4
  2.    /   \
  3.   2     7
  4.  / \   / \
  5. 1   3 6   9

输出：

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

备注:
这个问题是受到 Max Howell 的 原问题 启发的 ：

谷歌：我们90％的工程师使用您编写的软件(Homebrew)，但是您却无法在面试时在白板上写出翻转二叉树这道题，这太糟糕了。

解题方法：

解法一（利用递归算法）：

//递归算法中先序遍历
class Solution {
public:
    TreeNode* invertTree(TreeNode* root) 
    {
        if(root==nullptr)
            return nullptr;
        TreeNode* temp;
        temp=root->left;
        root->left=root->right;
        root->right=temp;
        invertTree(root->left);
        invertTree(root->right);
        return root;
    }
};
//递归算法中后序遍历
class Solution {
public:
    TreeNode* invertTree(TreeNode* root) 
    {
        if(root==nullptr)
            return nullptr;
        invertTree(root->left);
        invertTree(root->right);
        swap(root->right,root->left);
        return root;
    }
};

解法二（使用迭代算法，DFS）：

class Solution {
public: //DFS就需要用到栈
    TreeNode* invertTree(TreeNode* root) 
    {
        if(root==nullptr) return nullptr;
        stack<TreeNode*> s;
        TreeNode* temp;
        s.push(root);
        while(!s.empty())
        {
            temp=s.top();  //中
            s.pop();     //取出栈顶元素
            swap(temp->left,temp->right);  
            if(temp->left) s.push(temp->right);  //右
            if(temp->right) s.push(temp->left);  //左
        }
        return root;
    }
};

解法三（使用迭代算法，BFS）：

class Solution {
public: //BFS就需要用到队列
    TreeNode* invertTree(TreeNode* root) 
    {
        if(root==nullptr) return nullptr;
        queue<TreeNode*> que;
        que.push(root);
        while(!que.empty())
        {
            TreeNode* temp=que.front();
            que.pop();
            swap(temp->left,temp->right);
            if(temp->left) que.push(temp->left);
            if(temp->right) que.push(temp->right);
        }
        return root;
    }
};

做题小结：

针对解法一：

  1. 在使用递归时，可以选择只考虑递归的定义，而不需要去考虑递归的细节
  2. 交换可以使用一个函数swap()来进行

针对解法二：

  1. 熟悉stack的具体使用方法
  2. 在放入子树时，注意是中 右 左的顺序，因为想要先遍历左子树，那就应该最后放进去
  3. 一般stack用于前中后遍历的迭代算法

针对解法三：

  1. 熟悉queue的具体使用方法
  2. 一般queue用于层次遍历