二叉树的中序遍历
概述：给定一个二叉树的根节点 root ，返回它的中序遍历 。
输入：root = [1,null,2,3]
输出：[1,3,2]
输入：root = []
输出：[]
输入：root = [1]
输出：[1]
方法一：递归
思路：按照访问左子树——根节点——右子树的方式遍历这棵树，而在访问左子树或者右子树的时候我们按照同样的方式遍历，直到遍历完整棵树。因此整个遍历过程天然具有递归的性质，我们可以直接用递归函数来模拟这一过程。
# 递归
class Solution:
def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
if not root:
return []
left = ()
right = ()
return left + [] + right
# 递归另外一种写法
class Solution:
def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
def inorder(root:TreeNode):
if not root: # 空树
return []
inorder()
()
inorder()
res = []
inorder(root)
return res
方法二：迭代
思路：递归函数我们也可以用迭代的方式实现，两种方式是等价的，区别在于递归的时候隐式地维护了一个栈，而我们在迭代的时候需要显式地将这个栈模拟出来，其他都相同。
# 迭代
class Solution:
def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
res = []
if not root: # 空树
return []
stack = [] # 隐形栈
while stack or root:
while root:
(root) # 节点入栈
root =
root = () # 节点弹栈
()
root =
return res
# 迭代另外一种写法
class Solution:
def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
stack = []
def add_all_left(node):
while node:
(node)
node =
res = []
add_all_left(root)
while stack:
node = ()
()
add_all_left()
return res
方法三：Morris 中序遍历
思路：Morris 遍历算法是另一种遍历二叉树的方法。如果 x 无左孩子，先将 x 的值加入答案数组，再访问 x 的右孩子，即 x = 。如果 x 有左孩子，则找到 x 左子树上最右的节点（即左子树中序遍历的最后一个节点，x 在中序遍历中的前驱节点），我们记为 predecessor。根据 predecessor 的右孩子是否为空，进行如下操作。如果 predecessor 的右孩子为空，则将其右孩子指向 x，然后访问 x 的左孩子，即 x = 。如果 predecessor 的右孩子不为空，则此时其右孩子指向 x，说明我们已经遍历完 x 的左子树，我们将 predecessor 的右孩子置空，将 x 的值加入答案数组，然后访问 x 的右孩子，即 x = 。
# Morris 中序遍历
class Solution:
def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
res = []
while root:
if :
predecessor =
while :
predecessor =
= root
temp = root
root =
= None
else:
()
root =
return res
总结
递归真香！
