帮忙做ppt的网站,网站建设兼职平台,衡水网站建设电话,商城类网站建设篇目录 递归遍历前序遍历中序遍历后序遍历 迭代遍历前序遍历中序遍历后序遍历 递归遍历
前序遍历
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val0, leftNone, rightNone):
# self.val val
# self.left left
# … 目录 递归遍历前序遍历中序遍历后序遍历 迭代遍历前序遍历中序遍历后序遍历 递归遍历
前序遍历
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val0, leftNone, rightNone):
# 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, val0, leftNone, rightNone):
# 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, val0, leftNone, rightNone):
# 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, val0, leftNone, rightNone):
# 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, val0, leftNone, rightNone):
# 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, val0, leftNone, rightNone):
# 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]
