当前位置：首页 > news >正文

力扣热题100之二叉树的中序遍历

news 2025/5/31 17:58:34

题目

给定一个二叉树的根节点 root ，返回它的中序遍历。
在这里插入图片描述

代码

方法一：递归

在这里插入图片描述

class TreeNode:def __init__(self, val=0, left=None, right=None):self.val = valself.left = leftself.right = rightclass Solution:def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:result = []def traverse(node: Optional[TreeNode]):if not node:returntraverse(node.left)    # 递归左子树result.append(node.val) # 访问根节点traverse(node.right)    # 递归右子树traverse(root)return result

方法二：迭代

使用栈来代替左节点的递归

class TreeNode:def __init__(self, val=0, left=None, right=None):self.val = valself.left = leftself.right = rightclass Solution:def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:res=[]stack=[]cur=rootwhile cur or stack:while cur :stack.append(cur)cur=cur.leftcur=stack.pop()res.append(cur.val)cur=cur.rightreturn res

方法三：颜色标记

这是评论区中的一个方法，在每个节点之前使用1来标记节点是否每个子树的根节点，0标记每个子树的左右节点。
通过改变节点入栈的顺序来确定二叉树的遍历方法。因为栈具有先进后出的特点，所以在进行中序遍历的时候是右、中、左节点先后入栈，因为出栈的时候是左、中、右出栈。

class TreeNode:def __init__(self, val=0, left=None, right=None):self.val = valself.left = leftself.right = rightclass Solution:def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:WHITE,GRAY=0,1res=[]stack=[(WHITE,root)]while stack:color,node=stack.pop()if node is None:continueif color==WHITE:stack.append((WHITE,node.right))stack.append((GRAY,node))stack.append((WHITE,node.left))else:res.append(node.val)return res