25期代码随想录算法训练营第十四天 | 二叉树 | 递归遍历、迭代遍历

递归遍历

前序遍历

# 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]:if not root:return []left = self.preorderTraversal(root.left)right = self.preorderTraversal(root.right)return [root.val] + left + right

中序遍历

# 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]:if not root:return []left = self.inorderTraversal(root.left)right = self.inorderTraversal(root.right)return left + [root.val] + right

后序遍历

# 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]:if not root:return []left = self.postorderTraversal(root.left)right = self.postorderTraversal(root.right)return left + right + [root.val]

迭代遍历

前序遍历

# 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]:if not root:return []stack = [root]res = []while stack:cur = stack.pop()res.append(cur.val)  # 在这里加入节点值# 先右后左地加入子节点到栈中if cur.right:stack.append(cur.right)if cur.left:stack.append(cur.left)return res

中序遍历

为什么这样能实现左中右的逻辑？

为什么需要使用while cur or stack?

# 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]:if not root:return []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

后序遍历

中右左 ---->再颠倒顺序成为 左右中

# 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]:if not root:return []res = []stack = [root]while stack:node = stack.pop()res.append(node.val)if node.left:stack.append(node.left)if node.right:stack.append(node.right)return res[::-1]