O(n) time complexity and O(1) space complexity without recursive


  • 0
    S
    class Solution:
        # @param root, a tree node
        # @return a list of integers
        
        def inorderTraversal(self, root):
            res = []
            while root is not None:
                while root.left is not None:
                    # right rotate
                    left = root.left
                    root.left = left.right
                    left.right = root
                    root = left
                res.append(root.val)
                root = root.right
            return res

  • 0
    S

    Doesn't this method change the original tree structure?


  • 0
    S

    Yes, the original tree has changed. This is a problem, but the judger doesn't check it.


  • 0
    Z

    In your inner loop, left.right could be None


Log in to reply
 

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