一、基础知识点：

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);        
    }       
}

原文链接：https://blog.csdn.net/weixin_42042056/article/details/107081377