Morris inorder preorder O(n) O(1) space traversals threaded binary tree

class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        cur=root
        ans=[]
        while cur:
            if cur.left:
                pred=cur.left
                while pred.right and  pred.right!=cur:
                    pred=pred.right
                if pred.right==None:
                    pred.right=cur
                    cur=cur.left
                else:
                    pred.right=None
                    ans.append(cur.val)
                    cur=cur.right
            else:
                ans.append(cur.val)
                cur=cur.right
        return ans

class Solution:
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        cur=root
        ans=[]
        while cur:
            if not cur.left:
                ans.append(cur.val)
                cur=cur.right
            else:
                pred=cur.left
                while pred.right and pred.right!=cur:
                    pred=pred.right
                if pred.right==None:
                    pred.right=cur
                    ans.append(cur.val)
                    cur=cur.left
                else:
                    pred.right=None
                    cur=cur.right
        return ans
class Solution:
    def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        ans=[]
        cur=root
        while cur:
            if cur.right==None:
                ans.append(cur.val)
                cur=cur.left
            else:
                succ=cur.right
                while succ.left and succ.left!=cur:
                    succ=succ.left
                if succ.left==cur:
                    succ.left=None
                    cur=cur.left
                else:
                    ans.append(cur.val)
                    succ.left=cur
                    cur=cur.right
        return ans[::-1]