@@ -0,0 +1,1515 @@
+package depth_first_search;%0A%0Aimport public_class.TreeNode;%0A%0Aimport java.util.LinkedList;%0Aimport java.util.Queue;%0A%0Apublic class InvertBinaryTree %7B%0A%0A    //Difficulty: Easy%0A    //TAG: Uber%0A    //TAG: DFS%0A    //TAG: BFS%0A%0A    /**%0A     * 226. Invert Binary Tree%0A     * Invert a binary tree.%0A     *%0A     * Example:%0A     *%0A     * Input:%0A     *%0A     *      4%0A     *    /   %5C%0A     *   2     7%0A     *  / %5C   / %5C%0A     * 1   3 6   9%0A     * Output:%0A     *%0A     *      4%0A     *    /   %5C%0A     *   7     2%0A     *  / %5C   / %5C%0A     * 9   6 3   1%0A     */%0A%0A    /*%0A    Solution:%0A    DFS, assume that sub problem invertTree(left) invertTree(right) is ready, then just swap these two sub problem%0A%0A    Time: O(n)%0A    Space: O(n)%0A     */%0A%0A    public TreeNode invertTree(TreeNode root) %7B%0A        if (root == null) return null;%0A        TreeNode left = root.left, right = root.right;%0A        root.left = invertTree(right);%0A        root.right = invertTree(left);%0A        return root;%0A    %7D%0A%0A    /*%0A    Solution 2:%0A    BFS%0A     */%0A%0A    public TreeNode invertTree2(TreeNode root) %7B%0A        if (root == null) return null;%0A        final Queue%3CTreeNode%3E queue = new LinkedList%3C%3E();%0A        queue.offer(root);%0A        while(!queue.isEmpty()) %7B%0A            TreeNode node = queue.poll();%0A            TreeNode left = node.left;%0A            node.left = node.right;%0A            node.right = left;%0A            if(node.left != null) queue.offer(node.left);%0A            if(node.right != null) queue.offer(node.right);%0A        %7D%0A        return root;%0A    %7D%0A%0A%0A%0A%7D%0A

226. Invert Binary Tree