LeetCode 94. 二叉树的中序遍历(递归)(迭代)

题目描述

给定一个二叉树，返回它的后序遍历

思路

详见链接

代码

递归

#class TreeNode:
#	def __init__(self,x):
#		self.val = x
#		self.left = None
#		self.right = None

class Solution:
	def inorderTraversal(self,root:TreeNode):
		res = []
		def helper(root):
			if not root:
				return 
			helper(root.left)
			res.append(root.val)
			helper(root.right)
		helper(root)
		return res		

迭代

#class TreeNode:
#	def __init__(self,x):
#		self.val = x
#		self.left = None
#		self.right = None
		
class Solution:
	def inorderTraversal(self,root:TreeNode):
		res = []
		if not root:
			return res
		stack = []
		cur = root
		while stack or cur:
			while cur:
				stack.append(cur)
				cur = cur.left
			cur = stack.pop()
			res.append(cur.val)
			cur = cur.right
		return res