理论基础
-
种类
满二叉树：k是深度，node数为2^k - 1
完全二叉树：二叉树底部是从左向右持续的
二叉搜索树：左边节点都小于中间节点，右边节点都大于中间节点
平衡二叉树AVL：左边和右边高度相差不超过1 -
存储方式
链式存储：left child ptr, right child ptr
线式存储：字符数组保存，2i+1是左孩子，2i+2就是右孩子，很少用这个方式，可以实现层序遍历
class TreeNode:
def __init__(self, val, left = None, right = None):
self.val = val
self.left = left
self.right = right
前序遍历 PreOrder Traversal DLR 中左右
中序遍历 InOrder Traversal LDR 左中右
后序遍历 PostOrder Traversal LRD 左右中
D：Degree
L：Left
R：Right
递归遍历
# 前序遍历-递归-LC144_二叉树的前序遍历
# 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: TreeNode) -> List[int]:
if not root:
return []
left = self.preorderTraversal(root.left)
right = self.preorderTraversal(root.right)
return [root.val] + left + right
# 中序遍历-递归-LC94_二叉树的中序遍历
class Solution:
def inorderTraversal(self, root: TreeNode) -> List[int]:
if root is None:
return []
left = self.inorderTraversal(root.left)
right = self.inorderTraversal(root.right)
return left + [root.val] + right
# 后序遍历-递归-LC145_二叉树的后序遍历
class Solution:
def postorderTraversal(self, root: TreeNode) -> List[int]:
if not root:
return []
left = self.postorderTraversal(root.left)
right = self.postorderTraversal(root.right)
return left + right + [root.val]