思路:深度優先搜索dfs，時間復雜度0(n)。

C++版本：

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:TreeNode* invertTree(TreeNode* root) {if(root==nullptr) return root;TreeNode *Left= invertTree(root->left);TreeNode *Right=invertTree(root->right);root->left=Right;root->right=Left;return root;}
};

JAVA版本：

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

GO版本：

/*** Definition for a binary tree node.* type TreeNode struct {*     Val int*     Left *TreeNode*     Right *TreeNode* }*/
func invertTree(root *TreeNode) *TreeNode {if root==nil {return root}left:=invertTree(root.Left)right:=invertTree(root.Right)root.Left=rightroot.Right=leftreturn root
}