树总结

二叉树相关题目，用递归法最核心的思路是明确当前节点需要做的事情是什么

二叉树三种遍历

前序：根 --> 左节点 --> 右节点

中序：左节点 --> 根 --> 右节点

后序：左节点 --> 右节点 --> 根 

其实顺序根、右、左在逻辑上和前序是一样的，只是定义不同

同理右、左、根在逻辑上和后序一样

调试方法

在树节点定义中加入属性order，表示节点的序号，用于debug时定位树的遍历位置

def __init__(self, val=0, order=0, left=None, right=None):
    self.val = val
    self.left = left
    self.right = right
    self.order = order	#节点序号

1、BST二叉搜索树

代码框架

void BST(TreeNode root, int target) {
    if (root.val < target) 
        BST(root.right, target);
    else if (root.val > target)
        BST(root.left, target);
    else
    	// 找到目标，做点什么
}

序列化

即按一定顺序遍历树

用递归或非递归实现：前序、中序、后序

队列实现：层序

反序列化

即给一个序列，指定遍历方式，将其还原成树

给null节点：

1. 二叉树的序列化与反序列化

不给null节点：至少需要前序+中序，或后序+中序两个序列

105. 从前序与中序遍历序列构造二叉树

1. 从中序与后序遍历序列构造二叉树

Trie树（前缀树）

208.实现Trie(前缀树)

677. 键值映射

648.单词替换

211.添加与搜索单词-数据结构设计