1. /**
    2.  * 226. Invert Binary Tree
    3.  * <p>
    4.  * Given the root of a binary tree, invert the tree, and return its root.
    5.  * <p>
    6.  * <p>
    7.  * <p>
    8.  * Example 1:
    9.  * <p>
    10.  * <p>
    11.  * Input: root = [4,2,7,1,3,6,9]
    12.  * Output: [4,7,2,9,6,3,1]
    13.  * Example 2:
    14.  * <p>
    15.  * <p>
    16.  * Input: root = [2,1,3]
    17.  * Output: [2,3,1]
    18.  * Example 3:
    19.  * <p>
    20.  * Input: root = []
    21.  * Output: []
    22.  * <p>
    23.  * <p>
    24.  * Constraints:
    25.  * <p>
    26.  * The number of nodes in the tree is in the range [0, 100].
    27.  * -100 <= Node.val <= 100
    28.  */
    29. public class Lesson226 {
    31.     public static void main(String[] args) {
    32.         TreeNode root = Util.createTree(3);
    33.         Util.printBeforeTree(root);
    35.         new Solution().invertTree(root);
    36.         System.out.println("\n------");
    38.         Util.printBeforeTree(root);
    39.     }
    42.     /**
    43.      * Definition for a binary tree node.
    44.      */
    45.     private static class Solution {
    47.         public TreeNode invertTree(TreeNode root) {
    48.             revert(root);
    49.             return root;
    50.         }
    52.         private void revert(TreeNode node) {
    53.             if (node == null) return;
    55.             TreeNode tmp = node.left;
    56.             node.left = node.right;
    57.             node.right = tmp;
    58.             revert(node.left);
    59.             revert(node.right);
    61.         }
    63.     }
    65.     private static class Solution2 {
    67.         public TreeNode invertTree(TreeNode root) {
    68.             LinkedList<TreeNode> list = new LinkedList<>();
    69.             list.add(root);
    70.             while(!list.isEmpty()) {
    71.                 TreeNode curNode = list.poll();
    72.                 TreeNode tmp = curNode.left;
    73.                 curNode.left = curNode.right;
    74.                 curNode.right = tmp;
    75.                 if (curNode.left != null) {
    76.                     list.add(curNode.left);
    77.                 }
    78.                 if (curNode.right != null) {
    79.                     list.add(curNode.right);
    80.                 }
    81.             }
    82.             return root;
    83.         }
    85.     }
    87. }