1.满二叉树，完全二叉树，二叉搜索树（有数值，有序树）。
2.平衡二叉搜索树：又被称为AVL（Adelson-Velsky and Landis）树，且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
3.优先级队列其实是一个堆，堆就是一棵完全二叉树，同时保证父子节点的顺序关系。
4.二叉树可以链式存储（指针），也可以顺序存储（数组）。
5.二叉树主要有两种遍历方式：
- 深度优先遍历：先往深走，遇到叶子节点再往回走。
- 广度优先遍历：一层一层的去遍历。
6.栈其实就是递归的一种实现结构。
1 #二叉树的定义 2 class TreeNode: 3 def __init__(self,value): 4 self.value = value 5 self.left = None 6 self.right = None
java版本
1 //二叉树的定义 2 public class TreeNode{ 3 int val; 4 TreeNode left; 5 TreeNode right; 6 TreeNode() {} 7 TreeNode(int val) { 8 this.val = val; 9 } 10 TreeNode(int val, TreeNode left, TreeNode right){ 11 tihs.val = val 12 this.left = left 13 this.right = right 14 }
7.递归三要素：
-
确定递归函数的参数和返回值： 确定哪些参数是递归的过程中需要处理的，那么就在递归函数里加上这个参数， 并且还要明确每次递归的返回值是什么进而确定递归函数的返回类型。
-
确定终止条件： 写完了递归算法, 运行的时候，经常会遇到栈溢出的错误，就是没写终止条件或者终止条件写的不对，操作系统也是用一个栈的结构来保存每一层递归的信息，如果递归没有终止，操作系统的内存栈必然就会溢出。
-
确定单层递归的逻辑： 确定每一层递归需要处理的信息。在这里也就会重复调用自己来实现递归的过程。
144. 二叉树的前序遍历
【代码】
1 # Definition for a binary tree node. 2 # class TreeNode(object): 3 # def __init__(self, val=0, left=None, right=None): 4 # self.val = val 5 # self.left = left 6 # self.right = right 7 class Solution(object): 8 def preorderTraversal(self, root): 9 """ 10 :type root: TreeNode 11 :rtype: List[int] 12 """ 13 if not root: 14 return [] 15 16 left = self.preorderTraversal(root.left) 17 right = self.preorderTraversal(root.right) 18 19 return [root.val] + left + right
145. 二叉树的后序遍历
【代码】
1 # Definition for a binary tree node. 2 # class TreeNode(object): 3 # def __init__(self, val=0, left=None, right=None): 4 # self.val = val 5 # self.left = left 6 # self.right = right 7 class Solution(object): 8 def postorderTraversal(self, root): 9 """ 10 :type root: TreeNode 11 :rtype: List[int] 12 """ 13 if not root : 14 return [] 15 16 left = self.postorderTraversal(root.left) 17 right = self.postorderTraversal(root.right) 18 19 return left + right + [root.val]
94. 二叉树的中序遍历
【代码】
1 # Definition for a binary tree node. 2 # class TreeNode(object): 3 # def __init__(self, val=0, left=None, right=None): 4 # self.val = val 5 # self.left = left 6 # self.right = right 7 class Solution(object): 8 def inorderTraversal(self, root): 9 """ 10 :type root: TreeNode 11 :rtype: List[int] 12 """ 13 if not root : 14 return [] 15 16 left = self.inorderTraversal(root.left) 17 right = self.inorderTraversal(root.right) 18 19 return left + [root.val] + right
8.递归的实现就是：每一次递归调用都会把函数的局部变量、参数值和返回地址等压入调用栈中，然后递归返回的时候，从栈顶弹出上一次递归的各项参数，所以这就是递归为什么可以返回上一层位置的原因。
9.前序遍历是中左右，每次先处理的是中间节点，那么先将根节点放入栈中，然后将右孩子加入栈，再加入左孩子。
【代码】
1 class TreeNode(object): 2 def __init__(self, val=0, left=None, right=None): 3 self.val = val 4 self.left = left 5 self.right = right 6 7 8 def preorderTraversal(root: TreeNode): 9 # 根结点为空则返回空列表 10 if not root: 11 return [] 12 stack = [root] 13 result = [] 14 while stack: 15 node = stack.pop() 16 # 中结点先处理 17 result.append(node.val) 18 # 右孩子先入栈 19 if node.right: 20 stack.append(node.right) 21 # 左孩子后入栈 22 if node.left: 23 stack.append(node.left) 24 print(result) 25 26 if __name__ == '__main__': 27 root = TreeNode(1) 28 node1 = TreeNode(2) 29 node3 = TreeNode(3) 30 root.left = None 31 root.right = node1 32 node1.left = node3 33 preorderTraversal(root)
10.迭代法：前序遍历
【代码】
class Solution(object): def preorderTraversal(self, root): """ :type root: TreeNode :rtype: List[int] """ #1.递归法 # if not root: # return [] # left = self.preorderTraversal(root.left) # right = self.preorderTraversal(root.right) # return [root.val] + left + right #2.迭代法 if not root: # 根结点为空则返回空列表 return [] stack = [root] #栈 先将根节点入栈 result = [] #存放遍历结果 while stack: #栈不为空时 node = stack.pop() #将根节点弹出栈 #并将根节点的值存放在result中 result.append(node.val) #右孩子先入栈 if node.right:#当有右孩子的时候 stack.append(node.right) #左孩子后入栈 if node.left: stack.append(node.left) return result
11.迭代法：后序遍历:先序遍历是中左右——》调整代码左右顺序——》中右左——》反转result数组——》左右中
【代码】
1 class Solution(object): 2 def postorderTraversal(self, root): 3 """ 4 :type root: TreeNode 5 :rtype: List[int] 6 """ 7 #1.递归法 8 # if not root : 9 # return [] 10 11 # left = self.postorderTraversal(root.left) 12 # right = self.postorderTraversal(root.right) 13 14 # return left + right + [root.val] 15 16 #2.迭代法 17 if not root: 18 return [] 19 stack = [root] 20 result = [] 21 22 while stack: 23 node = stack.pop() 24 result.append(node.val) 25 #左孩子先入栈 26 if node.left: 27 stack.append(node.left) 28 #右 29 if node.right: 30 stack.append(node.right) 31 # 将最终的数组翻转 32 return result[::-1]
12.迭代法：中序遍历：
- 处理：将元素放进result数组中
- 访问：遍历节点
3.中序遍历是左中右，先访问的是二叉树顶部的节点，然后一层一层向下访问，直到到达树左面的最底部，再开始处理节点（也就是在把节点的数值放进result数组中），这就造成了处理顺序和访问顺序是不一致的。
4.借用指针的遍历来帮助访问节点，栈则用来记录遍历过的节点，再将处理过的元素放入result数组中。
1 class Solution(object): 2 def inorderTraversal(self, root): 3 """ 4 :type root: TreeNode 5 :rtype: List[int] 6 """ 7 #1.递归法 8 # if not root : 9 # return [] 10 11 # left = self.inorderTraversal(root.left) 12 # right = self.inorderTraversal(root.right) 13 14 # return left + [root.val] + right 15 16 #2.迭代法 17 #迭代终止条件 18 if not root: 19 return [] 20 stack = [] 21 result = [] 22 cur = root 23 24 while cur or stack: 25 # 先迭代访问最底层的左子树结点 26 if cur: 27 stack.append(cur) 28 cur = cur.left 29 # 到达最左结点后处理栈顶节点 30 else: 31 cur = stack.pop() 32 result.append(cur.val) 33 # 取栈顶元素右结点 34 cur = cur.right 35 36 return result
ps:记得之后看二叉树的统一迭代法