翻转一棵二叉树。

     4

    / \

   2   7

 / \  / \

1  3 6  9

转换为：

     4

    / \

   7    2

 / \    / \

9  6  3   1

详见：https://leetcode.com/problems/invert-binary-tree/

Java实现：

递归实现：

/** * Definition for a binary tree node. * public class TreeNode { *     int val; *     TreeNode left; *     TreeNode right; *     TreeNode(int x) { val = x; } * } */class Solution {    public TreeNode invertTree(TreeNode root) {        if(root==null){            return null;        }        TreeNode node=root.left;        root.left=invertTree(root.right);        root.right=invertTree(node);        return root;    }}

迭代实现：

/** * Definition for a binary tree node. * public class TreeNode { *     int val; *     TreeNode left; *     TreeNode right; *     TreeNode(int x) { val = x; } * } */class Solution {    public TreeNode invertTree(TreeNode root) {        if(root==null){            return null;        }        LinkedList
     
       que=new LinkedList
      
       ();        que.offer(root);        while(!que.isEmpty()){            TreeNode node=que.poll();            TreeNode tmp=node.left;            node.left=node.right;            node.right=tmp;            if(node.left!=null){                que.offer(node.left);            }            if(node.right!=null){                que.offer(node.right);            }        }        return root;    }}
      
     

C++实现：

方法一：

/** * 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==nullptr)        {            return nullptr;        }        TreeNode *node=root->left;        root->left=invertTree(root->right);        root->right=invertTree(node);        return root;    }};

方法二：

/** * 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==nullptr)        {            return nullptr;        }        queue
     
       que;        que.push(root);        while(!que.empty())        {            TreeNode *node=que.front();            que.pop();            TreeNode *tmp=node->left;            node->left=node->right;            node->right=tmp;            if(node->left)            {                que.push(node->left);            }            if(node->right)            {                que.push(node->right);            }        }        return root;    }};