@@ -0,0 +1,2850 @@
+package com.freetymekiyan.algorithms.level.medium;%0A%0Aimport com.freetymekiyan.algorithms.utils.Utils.TreeNode;%0A%0A/**%0A * Given a binary tree where all the right nodes are either leaf nodes with a sibling (a left node that shares the same%0A * parent node) or empty, flip it upside down and turn it into a tree where the original right nodes turned into left%0A * leaf nodes. Return the new root.%0A * %3Cp%3E%0A * For example:%0A * Given a binary tree %7B1,2,3,4,5%7D,%0A * %7C     1%0A * %7C    / %5C%0A * %7C   2   3%0A * %7C  / %5C%0A * %7C 4   5%0A * return the root of the binary tree %5B4,5,2,#,#,3,1%5D.%0A * %7C   4%0A * %7C  / %5C%0A * %7C 5   2%0A * %7C    / %5C%0A * %7C   3   1%0A * confused what %22%7B1,#,2,3%7D%22 means? %3E read more on how binary tree is serialized on OJ.%0A * %3Cp%3E%0A * Company Tags: LinkedIn%0A * Tags: Tree%0A * Similar Problems: (E) Reverse Linked List%0A */%0Apublic class BinaryTreeUpsideDown %7B%0A%0A    /**%0A     * Recursive.%0A     * Observations:%0A     * Leftmost child becomes the new root, suppose it's parent is p.%0A     * p's right child becomes the new root's left.%0A     * p itself becomes the new root's right.%0A     * Then set p to a leaf.%0A     * Return new root.%0A     * %3Cp%3E%0A     * Implementation:%0A     * Recurse down to the leftmost leaf, which is the new root.%0A     * From its parent p, we can set new root's left to p's right.%0A     * Then new root's right to p.%0A     * Finally disconnect p from both its children.%0A     * Move on to the previous parent.%0A     */%0A    public TreeNode upsideDownBinaryTree(TreeNode root) %7B%0A        if (root == null %7C%7C (root.left == null && root.right == null)) %7B%0A            return root;%0A        %7D%0A        TreeNode newRoot = upsideDownBinaryTree(root.left);%0A        root.left.left = root.right;%0A        root.left.right = root;%0A        root.left = null;%0A        root.right = null;%0A        return newRoot;%0A    %7D%0A%0A    /**%0A     * Iterative.%0A     * All right subtrees only have 1 node.%0A     * Move down along the left children.%0A     * While current node is not null:%0A     * %7C Store the next left child.%0A     * %7C Set current node's left to previous right.%0A     * %7C Update right to current right.%0A     * %7C Set current node's right to previous.%0A     * %7C Move on by updating prev to curr, curr to next.%0A     * Return prev.%0A     */%0A    public TreeNode upsideDownBinaryTreeB(TreeNode root) %7B%0A        TreeNode curr = root;%0A        TreeNode prev = null; // Previous root.%0A        TreeNode next = null; // Next node to flip.%0A        TreeNode right = null; // Previous right child.%0A%0A        while (curr != null) %7B%0A            // Store next.%0A            next = curr.left;%0A            // Swap nodes.%0A            curr.left = right; // Current left is previous right.%0A            right = curr.right; // Update right.%0A            curr.right = prev; // Current right is previous root.%0A            // Move on.%0A            prev = curr;%0A            curr = next;%0A        %7D%0A        return prev;%0A    %7D%0A%0A%7D%0A

add binary tree upside down