Two solutions: 1) 0ms O(1) space, 2) 2ms using stack


  • 0
    I

    Solution 1: using three variables to keep track of tree structure

    public class Solution {
            public TreeNode upsideDownBinaryTree(TreeNode root) {
                if(root == null){
                    return root;
                }
                TreeNode left = null, right = null, node = root;
                while(node != null){
                    TreeNode tempLeft = node.left;
                    TreeNode tempRight = node.right;
                    node.right = right;
                    node.left = left;
                    right = node;
                    left = tempRight;
                    node = tempLeft;
                }
                return right;
            }
        }
    

    Solution 2: using stack to track left most nodes of the tree

    public class Solution {
        public TreeNode upsideDownBinaryTree(TreeNode root) {
            if(root == null){
                return root;
            }
            Deque<TreeNode> stack = new LinkedList<>();
            TreeNode node = root;
            while(node != null){
                stack.addFirst(node);
                node = node.left;
            }
            TreeNode newRoot = stack.pop();
            node = newRoot;
            while(!stack.isEmpty()){
                TreeNode top = stack.pollFirst();
                node.right = top;
                if(top.right != null){
                    node.left = top.right;
                }
                else {
                    node.left = null;
                }
                node = top;
                top.left = null;
                top.right = null;
            }
            return newRoot;
        }
    }

Log in to reply
 

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