给定一个二叉树的根节点 root
,返回 它的 中序 遍历 。
示例 1:
输入:root = [1,null,2,3] 输出:[1,3,2]
示例 2:
输入:root = [] 输出:[]
示例 3:
输入:root = [1] 输出:[1]
提示:
- 树中节点数目在范围
[0, 100]
内 -100 <= Node.val <= 100
以下是一个Python程序,实现给定二叉树的中序遍历:
方案1:
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: TreeNode) -> List[int]: result = [] self.inorder(root, result) return result def inorder(self, root, result): if root is None: return self.inorder(root.left, result) result.append(root.val) self.inorder(root.right, result)
首先定义了一个 TreeNode 类表示二叉树的节点。然后定义了一个 Solution 类,其中有一个 inorderTraversal 方法用于计算二叉树的中序遍历。在这个方法中,我们创建一个空列表 result,然后调用 inorder 方法进行实际的遍历。
在 inorder 方法中,我们首先检查根节点是否为 None,如果是,则直接返回。否则,我们递归地遍历左子树,将根节点的值添加到结果列表中,然后递归地遍历右子树。最终返回结果列表 result。
方案2:
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: TreeNode) -> List[int]: result = [] stack = [] while root or stack: while root: stack.append(root) root = root.left root = stack.pop() result.append(root.val) root = root.right return result
首先定义了一个 TreeNode 类表示二叉树的节点。然后定义了一个 Solution 类,其中有一个 inorderTraversal 方法用于计算二叉树的中序遍历。在这个方法中,我们创建一个空列表 result 用于存储遍历结果,创建一个空栈 stack,用于辅助遍历操作。
使用while循环和栈来实现遍历,当root不为None或者栈不为空时,进入循环。首先将当前节点及其所有左子节点都压入栈中,然后从栈中弹出栈顶元素,将其值添加到结果列表 result 中。接下来,将当前节点的右子节点作为下一轮循环的起点,即将 root 赋值为 root.right,继续进行遍历操作。
最终,返回结果列表 result,即为二叉树的中序遍历结果。
标签:遍历,Python,中序,right,二叉树,root,self,result From: https://www.cnblogs.com/huadongw/p/17327356.html