Leetcode-226Invert Binary Tree

226. Invert Binary Tree

Invert a binary tree.

Example:

Input:

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

Output:

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

二叉树镜像(反转)；
先来个小插曲：今晚面试时被问到了这个问题，当时脑抽给出了一个炒鸡脑残的回答：二叉树宽搜+哈希表存递归深度和节点，再从右往左构建二叉树，，，，orz，，，
因为面试回答这道问题的时候直觉告诉我（哪里是直觉，应该是人类本能的认知），，自己的解答绝对不是最优的，，，于是乎，放下电话就开始重新思考这个问题，发现，炒鸡简单：
如图：输入一个二叉树，将二叉树反转，输出反转后的结果：
其实观察上图样例就能够发现，其实反转就是将每个节点的左右节点互换了而已，那么就简单了，我们只要在对二叉树深搜的过程中，将当前节点的左右节点互换下就可以了；
ps：小插曲2.0，其实介个问题很出名的，当时还有个小故事，当是小彩蛋附送啦：
https://www.zhihu.com/question/31187043?nr=1

My Solution(C/C++)

#include <iostream>
#include <cstdio>

using namespace std;

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

class Solution {
public:
    TreeNode * invertTree(TreeNode* root) {
        creatInvertTree(root);
        return root;
    }
    void printTree(TreeNode* node, int level) {
        if (!node) {
            return;
        }
        for (int i = 0; i < level; i++) {
            printf("-");
        }
        printf(" %d\n", node->val);
        printTree(node->left, level + 1);
        printTree(node->right, level + 1);
    }
private:
    void creatInvertTree(TreeNode* node) {
        if (!node) {
            return;
        }
        TreeNode *temp_node = node->left;
        node->left = node->right;
        node->right = temp_node;
        creatInvertTree(node->left);
        creatInvertTree(node->right);
    }
};

int main() {
    TreeNode a(4);
    TreeNode b(2);
    TreeNode c(7);
    TreeNode d(1);
    TreeNode e(3);
    TreeNode f(6);
    TreeNode g(9);
    a.left = &b;
    a.right = &c;
    b.left = &d;
    b.right = &e;
    c.left = &f;
    c.right = &g;
    Solution s;
    TreeNode *result;
    result = s.invertTree(&a);
    s.printTree(result, 0);
    return 0;
}

结果

 4
- 7
-- 9
-- 6
- 2
-- 3
-- 1