LeetCode算法解题集：Invert Binary Tree

题目：
Invert a binary tree.

 4

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

 4

/ \
7 2
/ \ / \
9 6 3 1
思路：
翻转二叉树，刚开始陷入了一个思维怪圈，认为先正向保存值至一个列表，然后再按照逆向还原这个链表，这种思路太复杂，如果是对称二叉树还好，非对称的就不好做。最后看了下别人的解题答案，很简单。先逆转最底层的两个节点，然后依次向上层逆转。算法复杂度：O（n）。
翻转过程如下：

 4

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

 4

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

 4

/ \
7 2
/ \ / \
9 6 3 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* invertTree(TreeNode* root)
{
    if (root != NULL)
    {
        root->left = invertTree(root->left);
        root->right = invertTree(root->right);

        //swich
        TreeNode *temp = root->left;
        root->left = root->right;
        root->right = temp;
    }

    return root;
}

};
总结：
1、该题困扰已久，主要还是思路问题，思路错了，再怎么折腾都是错的。
2、先找规律，再动手写代码。