学习资料：https://programmercarl.com/二叉树理论基础.html
二叉树：满二叉树、完全二叉树、二叉搜索数、平衡二叉搜索树；
链式存储、顺序存储；
前序/中序/后序遍历
递归法、迭代法，层序
深度优先搜索dfs，广度优先搜索
学习记录：
144.二叉树的前序遍历（也要注重二叉数的输入方式；递归法比迭代法好理解）
点击查看代码
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution(object):
def preorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
# 迭代法
result = []
stack = []
if root:
stack.append(root)
while stack:
node = stack.pop()
if node != None:
if node.right:
stack.append(node.right)
if node.left:
stack.append(node.left)
stack.append(node)
stack.append(None)
else:
node = stack.pop()
result.append(node.val)
return result
# 递归法
# res = []
# def dfs(node):
# """
# 深度优先搜索，前序遍历，根左右
# """
# if node is None:
# return
# res.append(node.val) # 根左右
# # 递归
# dfs(node.left)
# dfs(node.right)
# dfs(root)
# return res
94.二叉树的中序遍历
点击查看代码
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution(object):
def inorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
result = []
def dfs(node):
if node is None:
return
# 左根右
dfs(node.left)
result.append(node.val)
dfs(node.right)
dfs(root)
return result
145.二叉树的后序遍历
点击查看代码
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution(object):
def postorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
result = []
def dfs(node):
if node is None: # 判断节点是否为NULL，如果是就下一条遍历了
return
dfs(node.left) # 左右根
dfs(node.right)
result.append(node.val)
dfs(root)
return result
PS: 层序的十道题明天来完成，坐久了腰痛
阴转小雨，今晚吃了石锅拌饭，明白了人少有人少的道理，有点浪费原材料，不过还是吃的很开森，这不，又有力气干三道题了