模板手机网站建设,王也电脑壁纸,wordpress英文模板,中国建设网官方网站企业LeetCode-94. 二叉树的中序遍历【栈 树 深度优先搜索 二叉树】 题目描述#xff1a;解题思路一#xff1a;递归解题思路二#xff1a;迭代解题思路三#xff1a;0 题目描述#xff1a;
给定一个二叉树的根节点 root #xff0c;返回 它的 中序 遍历 。 示例 1#xff1… LeetCode-94. 二叉树的中序遍历【栈 树 深度优先搜索 二叉树】 题目描述解题思路一递归解题思路二迭代解题思路三0 题目描述
给定一个二叉树的根节点 root 返回 它的 中序 遍历 。 示例 1 输入root [1,null,2,3] 输出[1,3,2]
示例 2
输入root [] 输出[]
示例 3
输入root [1] 输出[1]
提示
树中节点数目在范围 [0, 100] 内 -100 Node.val 100
进阶: 递归算法很简单你可以通过迭代算法完成吗
解题思路一递归
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val0, leftNone, rightNone):
# self.val val
# self.left left
# self.right right
class Solution:def inorderTraversal(self, root: Optional[TreeNode]) - List[int]:if not root:return []left self.inorderTraversal(root.left)right self.inorderTraversal(root.right)return left [root.val] right时间复杂度O(n) 空间复杂度O(n)
解题思路二迭代
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val0, leftNone, rightNone):
# self.val val
# self.left left
# self.right right
class Solution:def inorderTraversal(self, root: Optional[TreeNode]) - List[int]:if not root:return []stack [] # 不能提前将root结点加入stack中res []cur rootwhile cur or stack:if cur:stack.append(cur)cur cur.leftelse:cur stack.pop()res.append(cur.val)cur cur.rightreturn res时间复杂度O(n) 空间复杂度O(n)
解题思路三0 时间复杂度O(n) 空间复杂度O(n)
