先序遍历
class Solution:
def preorderTraversal(self, root: TreeNode) -> List[int]:
result = []
stack = []
while root or len(stack) > 0:
while root:
result.append(root.val)
stack.append(root)
root = root.left
cur = stack.pop()
root = cur.right
return result
中序遍历
class Solution:
def inorderTraversal(self, root: TreeNode) -> List[int]:
result = []
stack = []
while root or len(stack) > 0:
while root:
stack.append(root)
root = root.left
cur = stack.pop()
result.append(cur.val)
root = cur.right
return result
后序遍历
class Solution:
def postorderTraversal(self, root: TreeNode) -> List[int]:
result = []
stack = []
prev = None
while root or len(stack) > 0:
while root:
stack.append(root)
root = root.left
cur = stack.pop()
# 如果该节点存在右子树，且右子树未被访问，则将该节点重新压入栈中
if cur.right and cur.right != prev:
stack.append(cur)
root = cur.right
else:
result.append(cur.val)
prev = cur
root = None
return result
当做一个记录，如果大家需要解释思路的话，不妨留言，我再补上思路～
