前序遍历
递归版本
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
result = []
if not root:
return result
result.append(root.val)
result += self.preorderTraversal(root.left)
result += self.preorderTraversal(root.right)
return result
非递归版本
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
result = []
if not root:
return result
stack = [root]
while stack:
cur = stack.pop()
result.append(cur.val)
if cur.right:
stack.append(cur.right)
if cur.left:
stack.append(cur.left)
return result
中序遍历
递归版本
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
result = []
if not root:
return result
result += self.inorderTraversal(root.left)
result.append(root.val)
result += self.inorderTraversal(root.right)
return result
非递归版本
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
result = []
if not root:
return result
stack = []
p = root
while stack or p:
# 将先根入栈，然后左节点入栈
while p:
stack.append(p)
p = p.left
# 左节点为空，根节点此时可以入栈，然后再看该节点的右节点
p = stack.pop()
result.append(p.val)
p = p.right
return result
Morris 遍历待补充
后序遍历
递归版本
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
result = []
if not root:
return result
result += self.postorderTraversal(root.left)
result += self.postorderTraversal(root.right)
result.append(root.val)
return result
非递归版本
搞懂了以后也比较简单，和中序遍历比较类似，不同的是后序遍历在右子树存在时需要先临时将根入栈，待右子树都处理完以后才能将根节点入栈。
这里面有个冲突就是：当判断某个根节点是否该被访问还是先将右子树进行访问的时候无法区分右子树是否已被访问过，所以需要一个prev标记一下。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
result = []
if not root:
return result
stack = []
p = root
prev = None
while stack or p:
while p:
stack.append(p)
p = p.left
p = stack.pop()
# 如果上一次访问过p的右子树或者右子树不存在
if prev == p.right or not p.right:
result.append(p.val)
prev = p
p = None
else:
stack.append(p)
p = p.right
return result
return result
