友情网站,网站建设属于什么,58网站怎么做优化,网站托管服务协议94. 二叉树的中序遍历
给定一个二叉树的根节点 root #xff0c;返回 它的 中序 遍历 。 示例 1#xff1a; 输入#xff1a;root [1,null,2,3]
输出#xff1a;[1,3,2]示例 2#xff1a;
输入#xff1a;root []
输出#xff1a;[]示例 3#xff1a;
输入#x…94. 二叉树的中序遍历
给定一个二叉树的根节点 root 返回 它的 中序 遍历 。 示例 1 输入root [1,null,2,3]
输出[1,3,2]示例 2
输入root []
输出[]示例 3
输入root [1]
输出[1]
方法一递归实现最简单
# Definition for a binary tree node.
class TreeNode:def __init__(self, val0, leftNone, rightNone):self.val valself.left leftself.right rightclass Solution:def inorderTraversal(self, root: TreeNode) - list[int]:result []def dfs(node):if not node:returndfs(node.left)result.append(node.val)dfs(node.right)dfs(root)return result方法二迭代实现使用栈
class Solution:def inorderTraversal(self, root: TreeNode) - list[int]:result []stack []current rootwhile current or stack:while current:stack.append(current)current current.left # 一直往左走current stack.pop()result.append(current.val)current current.right # 然后往右走return result
