My Java solution using stack(fixed memory limit exceed)


  • 0
    J

    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) {
                    stack.push(root);
                    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.