一、基础知识点：

1、树：

连通的无环图就是树 也要搞清楚下面的概念： 子树：左子树、右子树 根结点 父结点、祖先结点、子孙结点 子结点 兄弟结点 叶子结点 结点的度：结点的分支数 树的度：max(所有结点的度）

层 深度：最大的层（可以把根结点当作第一层，深度为1）

2、二叉树

1）二叉树：

是一种特殊的树，对于每个结点，如果最多有两个分支，即每个结点最多有两个子结点，分别叫做左子结点，和右子结点。

2）满二叉树：

除了叶子结点外，其他结点都有两个结点

3）完全二叉树：

除了最后一层以外，其他层的结点个数都达到最大，并且最后一层的叶子结点都靠左排列。 下图左边是满二叉树，右边是完全二叉树：

3、二叉树的存储

1）链式存储法（基于指针）

也就是像链表一样，每个结点有三个字段，一个存储数据，另外两个分别存放指向左右子结点的指针

2）顺序存储法（基于数组）

按照规律把结点存放在数组里，如下图所示，为了方便计算，我们会约定把根结点放在下标为 1 的位置，然后依次从上到下，从左到右遍历存储。 如果结点 X 的下标为 i，那么 X 的左子结点总是存放在 2 * i 的位置，X 的右子结点总是存放在 2 * i + 1 的位置。 之所以称为完全二叉树，是从存储空间利用效率的视角来看的。对于一棵完全二叉树而言，仅仅浪费了下标为 0 的存储位置。

4、二叉树的基本操作：

遍历的时间复杂度为O(N)，增删的复杂度为O(1)。

1）前序遍历：

简记为“根左右”，即先对该结点操作，然后递归遍历左子树，递归遍历右子树

2）中序遍历：

简记为：“左根右“

3）后序遍历：

简记为：“左右根” python的代码实现如下：

#先序遍历 res = [] def preorder(root): if not root: return #先根 res.append(root.val) preorder(root.left) preorder(root.right) #中序遍历 res = [] def inorder(root): if not root: return inorder(root.left) #中根 res.append(root.val) inorder(root.right) #后序遍历 res = [] def postorder(root): if not root: return postorder(root.left) postorder(root.right) #后根 res.append(root.val)

举例： 其前序遍历的结果为：[A,B,D,E,C,F,G]; 其中序遍历的结果为：[D,B,E,A,F,C,G]； 其后序遍历的结果为：[D,E,B,F,G,C,A]。

其前序遍历的结果为：[A,B,C,D,E,F,G,H,K]; 其中序遍历的结果为：[B,D,C,A,E,H,G,K,F]； 其后序遍历的结果为：[D,C,B,H,K,G,F,E,A]。

5、二叉搜索树(Binary Search Tree,简称BST)

1）特性

在二叉查找树中的任意一个结点，其左子树中的每个结点的值，都要小于这个结点的值。 在二叉查找树中的任意一个结点，其右子树中每个结点的值，都要大于这个结点的值。 任意结点的左右子树分别是二叉搜索树 在二叉查找树中，会尽可能规避两个结点数值相等的情况。 对二叉查找树进行中序遍历，就可以输出一个从小到大的有序数据队列。如下图所示，中序遍历的结果就是 10、13、15、16、20、21、22、26。

强调：对二叉搜索树中序遍历可以得到一个有序的数组。 当然我们可以判断一颗二叉树的合法性，注意，根结点不仅要小于右结点，还要小于右子树中的最小值；根结点不仅大于左节点，还要大于左子树中的最大值。 python代码如下：

def isValidBST(root): return self.helper(root,None,None) def helper(root,min_,max_): if not root: return True if not min_ and root.val <= min_.val: return False if not max_ and root.val >= max_val: return False return helper(root.left,min_,root) and helper(root.right,root,max_)

2）查找/遍历

在利用二叉查找树执行查找操作时，我们可以进行以下判断： 首先判断根结点是否等于要查找的数据，如果是就返回。 如果根结点大于要查找的数据，就在左子树中递归执行查找动作，直到叶子结点。 如果根结点小于要查找的数据，就在右子树中递归执行查找动作，直到叶子结点。 这样的“二分查找”所消耗的时间复杂度就可以降低为 O(logn)。

伪代码如下：

void BST(TreeNode root, int target) { if (root.val == target) // 找到目标 //根结点大于目标，说明目标在左子树中，在左子树中查找 if (root.val > target) BST(root.left, target); //根结点小于目标，说明目标在右子树中，在右子树中查找 if (root.val < target) BST(root.right, target); }

比如在二叉搜索树中查找target是否存在，python代码如下：

def isInBST(root,target): if not root: return False if root.val == target: return True if root.val > target: isInBST(root.left,target) if root.val < target: isInBST(root.right,target)

3）插入

从根结点开始，如果要插入的数据比根结点大，且根结点的右子结点不为空，则在根结点的右子树中继续尝试执行 插入操作。直到找到为空的子结点执行插入操作。 二叉查找树插入数据的时间复杂度是 O(logn)

其实就是遍历+访问，查找在上面写了伪代码，只需要改动一下，就可以：

TreeNode insertNumToBST(TreeNode root, int val) { // 找到空位置插入新节点 if (root == null) return new TreeNode(val); // if (root.val == val) // BST 中一般不会插入已存在元素 //根结点大于目标，说明目标在左子树中，在左子树中查找 if (root.val > val) root.left = insertNumToBST(root.left, val); //根结点小于目标，说明目标在右子树中，在右子树中查找 if (root.val < val) root.right = insertNumToBST(root.right, val); return root; }

4）删除

删除完某个结点后的树，仍要保证满足二叉搜索树的性质 情况一：如果要删除的结点时某个叶子结点，则直接删除，将其父结点指针指向null即可。 情况二：如果要删除的结点只有一个子结点，只需要将其父结点指向的子结点的指针换成其子结点的指针 情况三：如果要删除的结点有两个子结点，则有两种可行的操作方式 第一种：找到这个结点的左子树中最大的结点，替换要删除的结点 第二种：找到这个结点的右子树中最小的结点，替换要删除的结点。

也就是先“查”再“改”。 伪代码如下：

//情况1 if (root.left == null && root.right == null) return null; //情况 2 if (root.left == null) return root.right; if (root.right == null) return root.left; //情况3，这里是找右子树中的最小结点 if (root.left != null && root.right != null) { // 找到右子树的最小结点 TreeNode minNode = getMin(root.right); // 把 root 改成 minNode root.val = minNode.val; // 转而去删除 minNode root.right = deleteNode(root.right, minNode.val); }

注意：一般不会用root.val = minNode.val来修改结点的值。会通过链表指针的操作进行，具体碰到题的时候注意。 其中的getMin()函数：

TreeNode getMin(TreeNode node) { // BST 最左边的就是最小的 while (node.left != null) node = node.left; return node; }

整体的伪代码：

TreeNode deleteNode(TreeNode root, int target) { if (root.val == target) { // 找到，进行删除 } //根结点大于目标，说明目标在左子树中，在左子树中查找 else if (root.val > target) { root.left = deleteNode(root.left, target); } //根结点小于目标，说明目标在右子树中，在右子树中查找 else if (root.val < target) { root.right = deleteNode(root.right, target); } return root; }

整理一下：

TreeNode deleteNode(TreeNode root, int target) { if (root == null) return null if (root.val == target) { // 找到，进行删除 if (root.left == null) return root.right; if (root.right == null) return root.left; //情况3，这里是找右子树中的最小结点 // 找到右子树的最小结点 TreeNode minNode = getMin(root.right); // 把 root 改成 minNode root.val = minNode.val; // 转而去删除 minNode root.right = deleteNode(root.right, minNode.val); } //根结点大于目标，说明目标在左子树中，在左子树中查找 else if (root.val > target) { root.left = deleteNode(root.left, target); } //根结点小于目标，说明目标在右子树中，在右子树中查找 else if (root.val < target) { root.right = deleteNode(root.right, target); } return root; } TreeNode getMin(TreeNode node) { // BST 最左边的就是最小的 while (node.left != null) node = node.left; return node; }

二、 遍历框架

1、二叉树的遍历框架

基本的二叉树的遍历，包括前序遍历、中序遍历、后序遍历的框架

/* 基本的二叉树节点 */ /*class TreeNode { int val; TreeNode left, right; }*/ void traverse(TreeNode root) { //遍历左右子树 traverse(root.left) traverse(root.right) }

那么写成我们常见的框架就是：

void traverse(TreeNode root) { // 前序遍历，在这里操作 traverse(root.left) // 中序遍历，在这里操作 traverse(root.right) // 后序遍历，在这里操作 }

比如举几个例子：

1）把二叉树所有结点都+1

python代码实现如下：

def plusOne(root): if not root: return root.val += 1 plusOne(root.left) plusOne(root.right)

2）判断两个二叉树是否相同

python代码实现如下：

def isSameTree(root1,root2): if not root1 and not root2: return True if not root1 or not root2: return False if root1.val != root2.val: return False return isSameTree(root1.left,root.left) and isSameTree(root1.right,root2.right)

当然我们可以扩展到N叉树，从而可以扩展到图（因为树是特殊的图，可以参看数据结构和算法：从0到1-----图算法的基本概念）

2、N叉树的遍历框架：

/* 基本的 N 叉树节点 */ /*class TreeNode { int val; TreeNode[] children; }*/ void traverse(TreeNode root) { //遍历N个子树 for (TreeNode child : root.children) traverse(child); }

3、图的遍历框架：

void traverse(G) { for (g : G){ if (visited[child] == 1) continue traverse(g); } }