My Java solution using stack(fixed memory limit exceed)

  • 0

    Find the left most node by pushing nodes in the far left path. When changing the tree structure, you need to have a new node which is the parent node as the new right node, otherwise it would be cyclic.

    public class Solution {
            public TreeNode upsideDownBinaryTree(TreeNode root) {
                if (root == null) return root;
                Stack<TreeNode> stack = new Stack<TreeNode>();
                while (root != null) {
                    root = root.left;
                TreeNode newRoot = (TreeNode) stack.pop();
                TreeNode current = newRoot;
                while (!stack.empty()) {
                    TreeNode rnode = (TreeNode) stack.pop();
                    if (rnode.right != null) current.left = rnode.right;
                    current.right = new TreeNode(rnode.val);
                    current = current.right;
                return newRoot;

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.