Xiaohei's leetcode journey: 94. Inorder traversal of binary trees (supplementary Morris inorder traversal)

Xiaohei realizes after learning

# Definition for a binary tree node.# class TreeNode:# def __init__(self, val=0, left=None, right=None):# self.val = val# self.left = left# self.right = rightclass Solution:def inorderTraversal(self, root: Optional[TreeNode]span>) -> List[int]:arr = []while root:# pointer to left childpre = root.left# The left child is not empty (the "rightmost" node of the left child is connected to the root, and the root becomes the left child)if pre:# Find the rightmost childwhile pre.right and pre.right != root:pre = pre.right# The rightmost child points to root, then print root, then root is root.rightif pre.right:#pre.right = Nonearr.append(root.val)root = root.right# it is empty, point the right pointer of the rightmost child to root, then root = root.leftelse:pre.right = rootroot = root.left# left child is empty (print, root becomes right child)else:arr.append(root.val)root = root.rightreturn arr