给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。

示例 1：
image.png

输入：root = [4,2,7,1,3,6,9]
输出：[4,7,2,9,6,3,1]
示例 2：

输入：root = [2,1,3]
输出：[2,3,1]
示例 3：

输入：root = []
输出：[]

提示：

树中节点数目范围在 [0, 100] 内
-100 <= Node.val <= 100

  1. /**
  2.  * Definition for a binary tree node.
  3.  * public class TreeNode {
  4.  *     int val;
  5.  *     TreeNode left;
  6.  *     TreeNode right;
  7.  *     TreeNode() {}
  8.  *     TreeNode(int val) { this.val = val; }
  9.  *     TreeNode(int val, TreeNode left, TreeNode right) {
  10.  *         this.val = val;
  11.  *         this.left = left;
  12.  *         this.right = right;
  13.  *     }
  14.  * }
  15.  */
  16. class Solution {
  17.     public TreeNode invertTree(TreeNode root) {
  18.         if (root == null) return null;
  19.         Deque<TreeNode> stack = new LinkedList<>();
  20.         stack.push(root);
  21.         while (!stack.isEmpty()) {
  22.             TreeNode node = stack.poll();
  23.             if (node.right != null) stack.push(node.right);
  24.             if (node.left != null) stack.push(node.left);
  25.             TreeNode tem = node.left;
  26.             node.left = node.right;
  27.             node.right = tem;
  28.         }
  29.         return root;
  30.     }
  31. }

dfs

  1. /**
  2.  * Definition for a binary tree node.
  3.  * public class TreeNode {
  4.  *     int val;
  5.  *     TreeNode left;
  6.  *     TreeNode right;
  7.  *     TreeNode() {}
  8.  *     TreeNode(int val) { this.val = val; }
  9.  *     TreeNode(int val, TreeNode left, TreeNode right) {
  10.  *         this.val = val;
  11.  *         this.left = left;
  12.  *         this.right = right;
  13.  *     }
  14.  * }
  15.  */
  16. class Solution {
  17.     public TreeNode invertTree(TreeNode root) {
  18.         if (root == null) return null;
  19.         TreeNode left = root.left;
  20.         root.left = invertTree(root.right);
  21.         root.right = invertTree(left);
  22.         return root;
  23.     }
  24. }