翻转二叉树

问题

翻转前

翻转后

问题来源于Leetcode
https://leetcode.com/problems/invert-binary-tree/

问题分析

翻转一个二叉树，直观上看，就是把二叉树的每一层左右顺序倒过来。比如问题中的例子，第三层1-3-6-9经过变换后变成了9-6-3-1，顺序反过来就对了。
再仔细观察一下，对于上面的例子，根节点（root）的左子节点及其所有的子孙节点构成根节点的左子树（left subtree），同样的，根节点（root）的右子节点及其所有的子孙节点构成根节点的右子树（right subtree）。因此翻转一个二叉树，就是把根节点的左子树翻转一下，同样的把右子树翻转一下，在交换左右子树就可以了。
左子树和右子树
当然，翻转左子树和右子树的过程和当前翻转二叉树的过程没有区别，就是递归的调用当前的函数就可以了。

步骤总结如下：

• 翻转根节点的左子树（递归调用当前函数）
• 翻转根节点的右子树（递归调用当前函数）
• 交换根节点的左子节点与右子节点

程序代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution{
public:
void exchange(TreeNode* root){
    TreeNode* node=root;
    if(node!=NULL){
        TreeNode* temp=node->left;
        node->left=node->right;
        node->right=temp;
    }
} 
TreeNode* invertTree(TreeNode* root) {
    TreeNode* node=root;
    if(root==NULL) {
        return root;
    }
    invertTree(node->left);//翻转左子树
    invertTree(node->right);//翻转右子树
    exchange(node);//交换左子节点与右子节点
    return root;
}
};