public class TreeNode {int val;TreeNode left;TreeNode right;TreeNode(){}TreeNode(int val){this.val = val;}public TreeNode(int val, TreeNode left, TreeNode right) {this.val = val;this.left = left;this.right = right;}
}

/*
递归的进行翻转
保存原来的右子树*/
public class Solution1 {public TreeNode invertTree(TreeNode root){if(root == null){return null;}//保存右子树TreeNode rightTree = root.right;root.left = invertTree(root.right);root.right = invertTree(root.left);return root;}
}

import java.util.LinkedList;
import java.util.Queue;//层序遍历，使用队列
public class Solution2 {public TreeNode invertTree(TreeNode root){if(root == null){return null;}Queue<TreeNode> stack = new LinkedList<>();stack.offer(root);while(!stack.isEmpty()){TreeNode node = stack.poll();//保存右子树结点TreeNode rightTree = node.right;node.right = node.left;node.left = rightTree;if(node.left != null){stack.offer(node.left);}if(node.right != null){stack.offer(node.right);}}return root;}
}

public class Solution3 {public TreeNode invertTree(TreeNode root){if(root == null){return null;}TreeNode left = invertTree(root.left);TreeNode right = invertTree(root.right);root.right = left;root.left = right;return root;}
}