给定一个二叉树的根节点root,返回它的中序遍历结果。
数据范围:树上节点数满足 ,树上每个节点的值满足
进阶:空间复杂度 ,时间复杂度
进阶:空间复杂度 ,时间复杂度
{1,2,#,#,3}
[2,3,1]
{}
[]
{1,2}
[2,1]
{1,#,2}
[1,2]
树中节点数目在范围 [0, 100] 内树中的节点的值在[-100,100]以内
import sys class Solution: res=[] def inorderTraversal(self , root: TreeNode) -> List[int]: # 由于python存在最大的递归深度约束,这一步是更改最大深度的限制 sys.setrecursionlimit(1200)#大于树的深度 if not root: return [] self.inorderTraversal(root.left) self.res.append(root.val) self.inorderTraversal(root.right) return self.res
# 由于python存在最大的递归深度约束,需要更改最大深度的限制 import sys class Solution: def inOrder(self, root, arr): if root == None: return self.inOrder(root.left, arr) arr.append(root.val) self.inOrder(root.right, arr) def inorderTraversal(self , root: TreeNode) -> List[int]: sys.setrecursionlimit(1500)# 由于python存在最大的递归深度约束,这一步是更改最大深度的限制 alist = [] self.inOrder(root, alist) return alist
# class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None # # 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 # # # @param root TreeNode类 # @return int整型一维数组 # class Solution: def inorderTraversal(self , root: TreeNode) -> List[int]: # write code here if root is None: return [] inorderSeq = [] inorderSeq.append(root) # 当前节点是否已经经过 flag = [] flag.append(False) out = [] while inorderSeq: node = inorderSeq[-1] # 左子树非空或节点未经过,一直入栈,入栈的flag标记为True while node.left is not None and not flag[-1]: inorderSeq.append(node.left) flag[-1] = True flag.append(False) node = node.left # 当没有左子树或节点已经过,出栈并且输出 inorderSeq.pop() flag[-1] = True out.append(node.val) # 进入右子树 if node.right is not None: inorderSeq.append(node.right) flag.append(False) return out
import sys class Solution: def inorderTraversal(self , root: TreeNode) -> List[int]: # write code here sys.setrecursionlimit(2000) # 不改变递归最大值测试样例会报错 res = [] def inorder(root): if not root: return inorder(root.left) res.append(root.val) inorder(root.right) return inorder(root) return res
递归
import sys sys.setrecursionlimit(100000) class Solution: res = [] def dfs(self, root): if not root: return self.dfs(root.left) self.res.append(root.val) self.dfs(root.right) def inorderTraversal(self , root: TreeNode) -> List[int]: self.dfs(root) return self.res
import sys sys.setrecursionlimit(10000) class Solution: def __init__(self): self.l = [] def inorderTraversal(self , root: TreeNode) -> List[int]: # write code here if root == None: return self.inorderTraversal(root.left) self.l.append(root.val) self.inorderTraversal(root.right) return self.l
class Solution: def inorderTraversal(self , root: TreeNode) -> List[int]: # write code here if not root: return [] stack = [root] ret = [] while root.left: root = root.left stack.append(root) while stack: root = stack.pop() ret.append(root.val) if root.right: root = root.right stack.append(root) while root.left: root = root.left stack.append(root) return ret