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

  • 0
    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
                root = root.right
            return res

  • 0

    Doesn't this method change the original tree structure?

  • 0

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

  • 0

    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.