Easy O(n) iteration solution [Java]


  • 44
    Y
    public class Solution {
        public TreeNode UpsideDownBinaryTree(TreeNode root) {
            TreeNode curr = root;
            TreeNode prev = null;
            TreeNode next = null;
            TreeNode temp = null;
            
            while (curr != null) {
                next = curr.left;
                curr.left = temp;
                temp = curr.right;
                curr.right = prev;
                prev = curr;
                curr = next;
            }
            
            return prev;
        }
    }
    
    Just think about how you can save the tree information 
    you need before changing the tree structure.

  • 0
    S

    O(1) space is smart!


  • 1
    W

    'Just think about how you can save the tree information
    you need before changing the tree structure.' It's really nice that you explain how you come up with your idea.


  • 0
    B

    what if the input is {1,2,3,4,5,6},Will this code work?


  • 1
    A

    This is quite similar to reversing a linked list. This code really helped me see that. Thanks


  • 0
    Q

    Brilliant Solution! Need to scratch to figure it out.


Log in to reply
 

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