python-leetcode35.二叉树的中序遍历

给定一个二叉树的根节点root,返回它的中序遍历。

---

方法一：递归

二叉树的中序遍历：按照访问左子树——根节点——右子树的方式遍历这棵树，而在访问左子树或者右子树的时候我们按照同样的方式遍历，直到遍历完整棵树。因此整个遍历过程天然具有递归的性质

运行过程

从根节点 1 开始：

递归遍历左子树：1 的左子树为空，直接返回。

将 1 的值添加到结果列表 res 中：res = [1]。

递归遍历右子树：1 的右子树是 2。

进入节点 2：

递归遍历左子树：2 的左子树是 3。

进入节点 3：

递归遍历左子树：3 的左子树为空，直接返回。

将 3 的值添加到结果列表 res 中：res = [1, 3]。

递归遍历右子树：3 的右子树为空，直接返回。

将 2 的值添加到结果列表 res 中：res = [1, 3, 2]。

递归遍历右子树：2 的右子树为空，直接返回。

遍历结束，返回结果 res = [1, 3, 2]

# Definition for a binary tree node. # class TreeNode(object): # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution(object): def inorderTraversal(self, root): """ :type root: Optional[TreeNode] :rtype: List[int] """ res=[] #存储遍历结果 self.inorder(root,res) #中序遍历 return res def inorder(self,root,res): #递归函数，用于实现中序遍历 if not root: #如果当前节点 root 为空，直接返回 return self.inorder(root.left,res) res.append(root.val) #将当前节点的值 root.val 添加到结果列表 res 中 self.inorder(root.right,res)

时间复杂度：O(n)n为二叉树节点的个数

空间复杂度：O(n)

---

方法二：迭代

# Definition for a binary tree node. # class TreeNode(object): # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution(object): def inorderTraversal(self, root): """ :type root: Optional[TreeNode] :rtype: List[int] """ res=[] #空列表用于存储遍历结果 stack=[] #空列表用作栈来辅助遍历 while root or stack: #当 root 不为空或栈 stk 不为空时，继续循环 while root: #当root不为空时，将root推入栈stk中 stack.append(root) #将 root 移动到其左子节点 root=root.left #将当前节点的所有左子节点推入栈中，直到到达最左侧的节点 root=stack.pop() #从栈 stk 中弹出栈顶节点，赋值给 root,当前子树的最左侧节点 res.append(root.val) #将当前节点 root 的值 root.val 添加到结果列表 res 中 root=root.right #将 root 移动到其右子节点 return res

时间复杂度：O(n)

空间复杂度：O(n)

---

方法三：Morris中序遍历

Morris 遍历算法是另一种遍历二叉树的方法，它能将非递归的中序遍历空间复杂度降为O(1)。

Morris 遍历算法整体步骤如下（假设当前遍历到的节点为x）：

1.如果x无左孩子，先将x的值加入答案数组，再访问x的右孩子，即x=x.right

2.如果x有左孩子，则找到x左子树上最右的节点（即左子树中序遍历的最后一个节点x,x在中序遍历中的前驱节点），记为predecessor。根据predecessor的右孩子是否为空，进行如下操作:

如果predecessor的右孩子为空，则将其右孩子指向x，然后访问x的左孩子，即x=x.left。

如果predecessor的右孩子不为空，则此时其右孩子指向x，说明已经遍历完x的左子树，将predecessor的右孩子置空，将x的值加入答案数组，然后访问x的右孩子，即x=x.right。

# Definition for a binary tree node. # class TreeNode(object): # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution(object): def inorderTraversal(self, root): """ :type root: Optional[TreeNode] :rtype: List[int] """ res=[] #列表，用来存储最终的中序遍历结果 predcessor=None #当前节点的前驱节点（即，当前节点的左子树中最右边的节点） while root: #只要当前节点不为空，就继续遍历 if root.left: predcessor=root.left #predecessor 节点就是当前 root 节点向左走一步，然后一直向右走至无法走为止 while predcessor.right and predcessor.right != root: predcessor=predcessor.right if predcessor.right is None: #predecessor 的右指针指向 root，继续遍历左子树 predcessor.right=root #前驱节点的右子树为空，把它的右子树指向当前节点 root root=root.left #移动到它的左子树，继续遍历 else:#前驱节点的右子树指向了当前节点，说明左子树遍历完成，可以访问当前节点 res.append(root.val) predcessor.right=None root=root.right else:#当前节点没有左子树，直接访问当前节点，并将 root 移动到右子树 res.append(root.val) root=root.right return res

时间复杂度：O(n)

空间复杂度：O(1)