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、先找规律，再动手写代码。

本文摘录于海阔天空的博客，作者: zjg555543，发布时间: 2015-09-08