@@ -0,0 +1,1934 @@
+package problems;%0A%0Aimport java.util.Stack;%0A%0Apublic class BinaryTreeUpsideDown %7B%0A%0A    class TreeNode %7B%0A        int val;%0A        TreeNode left, right;%0A%0A        public TreeNode(int value) %7B%0A            this.val = value;%0A        %7D%0A    %7D%0A%0A    public final TreeNode upsideDownBinaryTree(TreeNode root) %7B%0A        // recursive solution%0A        if (root == null %7C%7C root.left == null)%0A            return root;%0A%0A        final TreeNode parent = root.left;%0A        final TreeNode head = upsideDownBinaryTree(parent);%0A        parent.left = root.right;%0A        parent.right = root;%0A        root.left = root.right = null;%0A        return head;%0A    %7D%0A%0A    public final TreeNode upsideDownBinaryTree2(TreeNode root) %7B%0A        // iterative solution using stack%0A        Stack%3CTreeNode%3E st = new Stack%3CTreeNode%3E();%0A        TreeNode left = root;%0A        while (left != null) %7B%0A            st.push(left);%0A            left = left.left;%0A        %7D%0A        TreeNode head = st.isEmpty() ? null : st.pop();%0A        TreeNode parent = head;%0A        while (st.size() %3E 0) %7B%0A            TreeNode t = st.pop();%0A            parent.right = t;%0A            parent.left = t.right;%0A            t.left = t.right = null;%0A            parent = t;%0A        %7D%0A        return head;%0A    %7D%0A%0A    void PreorderPrintTree(TreeNode root) %7B%0A        if (root == null)%0A            System.out.print(%22#,%22);%0A        else %7B%0A            System.out.print(root.val + %22,%22);%0A            PreorderPrintTree(root.left);%0A            PreorderPrintTree(root.right);%0A        %7D%0A    %7D%0A%0A    public static void main(String%5B%5D args) %7B%0A        BinaryTreeUpsideDown ud = new BinaryTreeUpsideDown();%0A%0A        TreeNode root = ud.new TreeNode(1);%0A        root.left = ud.new TreeNode(2);%0A        root.right = ud.new TreeNode(3);%0A        root.left.left = ud.new TreeNode(4);%0A        root.left.right = ud.new TreeNode(5);%0A%0A        TreeNode head = ud.upsideDownBinaryTree2(root);%0A        ud.PreorderPrintTree(head);%0A    %7D%0A%7D%0A

Add Binary Tree Upside Down