小黑leetcode之旅:94. 二叉树的中序遍历(补充Morris 中序遍历)

小黑学习后实现

# 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 = right
class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        arr = []
        while root:
            # 指针指向左孩子
            pre = root.left
            # 左孩子不为空(左孩子"最右"结点连接root,root变为左孩子)
            if pre:
            	# 寻找最右孩子
                while pre.right and pre.right != root:
                    pre = pre.right
                # 最右孩子指向root,则打印root，随后root为root.right
                if pre.right:
                    #pre.right = None
                    arr.append(root.val)
                    root = root.right
                # 其为空，将最右孩子的右侧指针指向root，然后将root = root.left
                else:
                    pre.right = root
                    root = root.left

            # 左孩子为空(打印，root变为右孩子)
            else:
                arr.append(root.val)
                root = root.right
        return arr