树结构的学习：(摘抄代码随想录的部分笔记)

starting !

叉树理论基础篇

题目分类大纲如下：

二叉树的种类

在我们解题过程中二叉树有两种主要的形式：满二叉树和完全二叉树。

满二叉树

满二叉树：如果一棵二叉树只有度为0的结点和度为2的结点，并且度为0的结点在同一层上，则这棵二叉树为满二叉树。

如图所示：

这棵二叉树为满二叉树，也可以说深度为k，有2^k-1个节点的二叉树。

完全二叉树

什么是完全二叉树？

完全二叉树的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2^(h-1) 个节点。

大家要自己看完全二叉树的定义，很多同学对完全二叉树其实不是真正的懂了。

一个典型的例子：

之前我们刚刚讲过优先级队列其实是一个堆，堆就是一棵完全二叉树，同时保证父子节点的顺序关系。

二叉搜索树

前面介绍的树，都没有数值的，而二叉搜索树是有数值的了，二叉搜索树是一个有序树。

若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
它的左、右子树也分别为二叉排序树

下面这两棵树都是搜索树

平衡二叉搜索树

平衡二叉搜索树：又被称为AVL（Adelson-Velsky and Landis）树，且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

如图：

最后一棵不是平衡二叉树，因为它的左右两个子树的高度差的绝对值超过了1。

C++中map、set、multimap，multiset的底层实现都是平衡二叉搜索树，所以map、set的增删操作时间时间复杂度是logn，注意我这里没有说unordered_map、unordered_set，unordered_map、unordered_set底层实现是哈希表。

二叉树的存储方式

二叉树可以链式存储，也可以顺序存储。

那么链式存储方式就用指针，顺序存储的方式就是用数组。

顾名思义就是顺序存储的元素在内存是连续分布的，而链式存储则是通过指针把分布在各个地址的节点串联一起。

链式存储如图：

链式存储其实就是用数组来存储二叉树，顺序存储的方式如图：

用数组来存储二叉树如何遍历的呢？

如果父节点的数组下标是 i，那么它的左孩子就是 i * 2 + 1，右孩子就是 i * 2 + 2。

但是用链式表示的二叉树，更有利于我们理解，所以一般我们都是用链式存储二叉树。

所以大家要了解，用数组依然可以表示二叉树。

二叉树的遍历方式

二叉树主要有两种遍历方式：

深度优先遍历：先往深走，遇到叶子节点再往回走。
广度优先遍历：一层一层的去遍历。

这两种遍历是图论中最基本的两种遍历方式，后面在介绍图论的时候还会介绍到。

那么从深度优先遍历和广度优先遍历进一步拓展，才有如下遍历方式：

深度优先遍历
- 前序遍历（递归法，迭代法）
- 中序遍历（递归法，迭代法）
- 后序遍历（递归法，迭代法）
广度优先遍历
- 层次遍历（迭代法）

在深度优先遍历中：有三个顺序，前中后序遍历，有同学总分不清这三个顺序，经常搞混，我这里教大家一个技巧。

这里前中后，其实指的就是中间节点的遍历顺序，只要大家记住前中后序指的就是中间节点的位置就可以了。

看如下中间节点的顺序，就可以发现，中间节点的顺序就是所谓的遍历方式

前序遍历：中左右
中序遍历：左中右
后序遍历：左右中

大家可以对着如下图，看看自己理解的前后中序有没有问题。

最后再说一说二叉树中深度优先和广度优先遍历实现方式，我们做二叉树相关题目，经常会使用递归的方式来实现深度优先遍历，也就是实现前中后序遍历，使用递归是比较方便的。

之前我们讲栈与队列的时候，就说过栈其实就是递归的一种实现结构，也就说前中后序遍历的逻辑其实都是可以借助栈使用非递归的方式来实现的。

而广度优先遍历的实现一般使用队列来实现，这也是队列先进先出的特点所决定的，因为需要先进先出的结构，才能一层一层的来遍历二叉树。

这里其实我们又了解了栈与队列的一个应用场景了。

二叉树的定义

刚刚我们说过了二叉树有两种存储方式顺序存储，和链式存储，顺序存储就是用数组来存，这个定义没啥可说的，我们来看看链式存储的二叉树节点的定义方式。

C++代码如下：

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

大家会发现二叉树的定义和链表是差不多的，相对于链表，二叉树的节点里多了一个指针，有两个指针，指向左右孩子。

二叉树的遍历

一棵树的三种遍历方式:先序遍历,中序遍历,后序遍历。

先序遍历访问顺序: 1.根节点 2.左子树 3.右子树这里根节点是最优先级,因为是先序(根节点放最前)
中序遍历访问顺序: 1.左子树 2.根节点 3.右子树因为是中序,所以根节点就放在了中间。
后序遍历访问顺序: 1.左子树 2.右子树 3.根节点后序,所以根节点放在最后

递归遍历

递归算法的三个要素。

确定递归函数的参数和返回值： 确定哪些参数是递归的过程中需要处理的，那么就在递归函数里加上这个参数，并且还要明确每次递归的返回值是什么进而确定递归函数的返回类型。
确定终止条件： 写完了递归算法, 运行的时候，经常会遇到栈溢出的错误，就是没写终止条件或者终止条件写的不对，操作系统也是用一个栈的结构来保存每一层递归的信息，如果递归没有终止，操作系统的内存栈必然就会溢出。
确定单层递归的逻辑： 确定每一层递归需要处理的信息。在这里也就会重复调用自己来实现递归的过程。
确定递归函数的参数和返回值：因为要打印出前序遍历节点的数值，所以参数里需要传入vector来放节点的数值，除了这一点就不需要再处理什么数据了也不需要有返回值，所以递归函数返回类型就是void，代码如下：

void traversal(TreeNode* cur, vector<int>& vec)

确定终止条件：在递归的过程中，如何算是递归结束了呢，当然是当前遍历的节点是空了，那么本层递归就要结束了，所以如果当前遍历的这个节点是空，就直接return，代码如下：

if (cur == NULL) return;

确定单层递归的逻辑：前序遍历是中左右的循序，所以在单层递归的逻辑，是要先取中节点的数值，代码如下：

vec.push_back(cur->val);    // 中
traversal(cur->left, vec);  // 左
traversal(cur->right, vec); // 右

单层递归的逻辑就是按照中左右的顺序来处理的，这样二叉树的前序遍历，基本就写完了，再看一下完整代码：

前序遍历：

class Solution {
public:
    void traversal(TreeNode* cur, vector<int>& vec) {
        if (cur == NULL) return;
        vec.push_back(cur->val);    // 中
        traversal(cur->left, vec);  // 左
        traversal(cur->right, vec); // 右
    }
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> result;
        traversal(root, result);
        return result;
    }
};

那么前序遍历写出来之后，中序和后序遍历就不难理解了，代码如下：

中序遍历：

void traversal(TreeNode* cur, vector<int>& vec) {
    if (cur == NULL) return;
    traversal(cur->left, vec);  // 左
    vec.push_back(cur->val);    // 中
    traversal(cur->right, vec); // 右
}

后序遍历：

void traversal(TreeNode* cur, vector<int>& vec) {
    if (cur == NULL) return;
    traversal(cur->left, vec);  // 左
    traversal(cur->right, vec); // 右
    vec.push_back(cur->val);    // 中
}

迭代遍历

先序遍历

先序遍历是中左右，每次处理的是中间结点先将根节点放入栈中，然后将右孩子加入栈，再加入左孩子。先加入右孩子才能保证出栈时中左右的顺序。

代码：

class Solution{
public:
    vector<int> preorderTraversal(TreeNode* root) {
        stack<TreeNode*> st;
        vector<int>result;
        if(root == NULL) return result;
        st.push(root);
        while(!st.empty()){
            TreeNode* node = st.top();
            st.pop();
            if(node->right) st.push(node->right);
            if(node->left) st.push(node->left);
		}
        return result;
    }
};

中序遍历

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> result;
        stack<TreeNode*> st;
        TreeNode* cur = root;
        while (cur != NULL || !st.empty()) {
            if (cur != NULL) { // 指针来访问节点，访问到最底层
                st.push(cur); // 将访问的节点放进栈
                cur = cur->left;                // 左
            } else {
                cur = st.top(); 
                // 从栈里弹出的数据，就是要处理的数据（放进result数组里的数据）
                st.pop();
                result.push_back(cur->val);     // 中
                cur = cur->right;               // 右
            }
        }
        return result;
    }
};

后序遍历

将先序遍历的左右结点遍历顺序交换即可

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        stack<TreeNode*> st;
        vector<int> result;
        if (root == NULL) return result;
        st.push(root);
        while (!st.empty()) {
            TreeNode* node = st.top();
            st.pop();
            result.push_back(node->val);
            if (node->left) st.push(node->left); 
            // 相对于前序遍历，这更改一下入栈顺序 （空节点不入栈）
            if (node->right) st.push(node->right); // 空节点不入栈
        }
        reverse(result.begin(), result.end()); // 将结果反转之后就是左右中的顺序了
        return result;
    }
};

迭代遍历的统一代码

中序遍历

class Solution{
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> result;
        stack<TreeNode*> st;
        if(root != NULL) st.push(root);
        while(!st.empty()){
            TreeNode* node = st.top();
            if(node != NULL){
                st.pop(); //将该节点弹出避免重复操作，下面再将左中节点添加到栈中
                if(node->right) st.push(node->right); //添加右节点
                st.push(node);
                st.push(NULL); //中节点访问过，但是还没有进行处理，加入空节点作为标记
                if(node->left) st.push(node->left);
            }else{ //只有遇到空节点的时候，才将下一个节点放进结果集
                st.pop(); // 将空节点弹出
                node = st.top(); //重新取出栈中元素
                st.pop();
                result.push_back(node->val);//加入结果集
            }
        }
    }
};

前序遍历

class Solution{
public:
    vector<int> preorderTraversal(TreeNode* root){
        vector<int> result;
        stack<TreeNode*> st;
        if(root != NULL) st.push(root);
        while(!st.empty*=()){
            TreeNode* node = st.top();
            if(node != NULL){
                st.pop();
                if(node->right) st.push(node->right); //右
                if(node->left) st.push(node->left);   //左
                st.push(node);    //中
                st.push(NULL);
			}else{
                st.pop();
                node = st.top();
                st.pop();
                result.push_back(node->val);
			}
		}
    }
};

层序遍历 | 广度优先搜索

层序遍历，就是一层一层从左往右遍历二叉树。

需要借助数据结构队列来实现二叉树的层序迭代遍历，队列先进先出，符合一层一层遍历的逻辑，而用栈先进后出的逻辑适合模拟深度优先搜索，也就是递归的逻辑。

而这种层序遍历方式就是图论中的 广度优先遍历，这种思想可以应用于二叉树上。

使用队列实现 二叉树的广度优先遍历

模板代码：

class Solution{
public:
    vector<vector<int>> levelOrder(TreeNode* root){
        queue<TreeNode*> que;
        if(root != NULL) que.push(root);
        vector<vector<int>> result;
        while(!que.empty()){
            int size = que.size();
            vector<int> vec;
	//这里一定要使用固定大小 size，不要使用 que.size()，因为 que.size()是变化的
            for(int i = 0; i<size; i++){
                TreeNode* node = que.front();
                que.pop();
                vec.push_back(node->val);
                if(node->left) que.push(node->left);
                if(node->right) que.push(node->right);
            }
            res.push_back(v);
		}
    }
};

二叉搜索树中的搜索

力扣700

给定二叉搜索树（BST）的根节点 root 和一个整数值 val。

你需要在 BST 中找到节点值等于 val 的节点。返回以该节点为根的子树。如果节点不存在，则返回 null 。

示例 1:

输入：root = [4,2,7,1,3], val = 2
输出：[2,1,3]

示例 2:

输入：root = [4,2,7,1,3], val = 5
输出：[]

提示：

数中节点数在 [1, 5000] 范围内
1 <= Node.val <= 107
root 是二叉搜索树
1 <= val <= 107

递归法：

class Solution {
public:
    TreeNode* searchBST(TreeNode* root, int val) {
        if (root == NULL || root->val == val) return root;
        if (root->val > val) return searchBST(root->left, val);
        if (root->val < val) return searchBST(root->right, val);
        return NULL;
    }
};

迭代法：

class Solution {
public:
    TreeNode* searchBST(TreeNode* root, int val) {
        while (root != NULL) {
            if (root->val > val) root = root->left;
            else if (root->val < val) root = root->right;
            else return root;
        }
        return NULL;
    }
};

例题

二叉树的最大深度

力扣104

给定一个二叉树，找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。

示例： 给定二叉树 [3,9,20,null,null,15,7]，

返回它的最大深度 3 。

超级简洁的代码：

class Solution {
public:
    int maxDepth(TreeNode* root) {
        return (root == NULL)?max(maxDepth(root->left), maxDepth(root->right))+1;
    }
};

二叉树的最近公共祖先

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

示例 1：

输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出：3
解释：节点 5 和节点 1 的最近公共祖先是节点 3 。

示例 2：

输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出：5
解释：节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。

示例 3：

输入：root = [1,2], p = 1, q = 2
输出：1

提示：

树中节点数目在范围 [2, 105] 内。
-109 <= Node.val <= 109
所有 Node.val 互不相同 。
p != q
p 和 q 均存在于给定的二叉树中。

大佬的代码：

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (!root || root == p || root == q) return root;
        TreeNode *left = lowestCommonAncestor(root->left, p, q);
        TreeNode *right = lowestCommonAncestor(root->right, p, q);
        if (left && right) return root;
        return left ? left : right;
    }
};

二叉搜索树的最近公共祖先

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

例如，给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5]

示例 1:

输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
输出: 6 
解释: 节点 2 和节点 8 的最近公共祖先是 6。

示例 2:

输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
输出: 2
解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。

说明:

所有节点的值都是唯一的。
p、q 为不同节点且均存在于给定的二叉搜索树中。

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(root->val > p->val && root->val > q->val)
            return lowestCommonAncestor(root->left, p, q);
        else if(root->val < p->val && root->val < q->val)
            return lowestCommonAncestor(root->right, p, q);
        return root;
    }
};

二叉搜索树中的插入操作

给定二叉搜索树（BST）的根节点 root 和要插入树中的值 value ，将值插入二叉搜索树。返回插入后二叉搜索树的根节点。输入数据保证，新值和原始二叉搜索树中的任意节点值都不同。

注意，可能存在多种有效的插入方式，只要树在插入后仍保持为二叉搜索树即可。你可以返回 任意有效的结果 。

示例 1：

输入：root = [4,2,7,1,3], val = 5
输出：[4,2,7,1,3,5]
解释：另一个满足题目要求可以通过的树是：

示例 2：

输入：root = [40,20,60,10,30,50,70], val = 25
输出：[40,20,60,10,30,50,70,null,null,25]

示例 3：

输入：root = [4,2,7,1,3,null,null,null,null,null,null], val = 5
输出：[4,2,7,1,3,5]

提示：

树中的节点数将在 [0, 104]的范围内。
-108 <= Node.val <= 108
所有值 Node.val 是 独一无二 的。
-108 <= val <= 108
保证 val 在原始BST中不存在。

DFS(深度优先) 关键点： 1：采用DFS遍历树，遍历所有的结点 2：因为是二叉搜素树，所以结点的值，还按照规律的 3：左子树的值一定小于根结点的值 4：右子树的值一定大于根结点的值 5：根据Vaule与root结点的值比较，选择遍历左或右子树 6：找到空的结点插入对应的值即可

时间复杂度：空间复杂度:

class Solution {
public:
    TreeNode* insertIntoBST(TreeNode* root, int val) {
        if(root == NULL) return new TreeNode(val);
        if(root->val < val) root->right = insertIntoBST(root->right, val);
        else root->left = insertIntoBST(root->left, val);
        return root;
    }
};

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

力扣106

给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。

示例 1:

输入：inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
输出：[3,9,20,null,null,15,7]

示例 2:

输入：inorder = [-1], postorder = [-1]
输出：[-1]

提示:

1 <= inorder.length <= 3000
postorder.length == inorder.length
-3000 <= inorder[i], postorder[i] <= 3000
inorder 和 postorder 都由不同的值组成
postorder 中每一个值都在 inorder 中
inorder 保证是树的中序遍历
postorder 保证是树的后序遍历

思路:

以后序数组的最后一个元素为切割点，先切中序数组，根据中序数组，反过来再切后序数组。一层一层切下去，每次后序数组最后一个元素就是节点元素。

流程如图：

那么代码应该怎么写呢？

说到一层一层切割，就应该想到了递归

一共分六步：

第一步：如果数组大小为零的话，说明是空节点了。
第二步：如果不为空，那么取后序数组最后一个元素作为节点元素。
第三步：找到后序数组最后一个元素在中序数组的位置，作为切割点
第四步：切割中序数组，切成中序左数组和中序右数组（顺序别搞反了，一定是先切中序数组）
第五步：切割后序数组，切成后序左数组和后序右数组
第六步：递归处理左区间和右区间

为了高效查找根节点元素在中序遍历数组中的下标，我们选择创建哈希表来存储中序序列，即建立一个（元素，下标）键值对的哈希表。
定义递归函数 helper(in_left, in_right) 表示当前递归到中序序列中当前子树的左右边界，递归入口为helper(0, n - 1) ：
- 如果 in_left > in_right，说明子树为空，返回空节点。
- 选择后序遍历的最后一个节点作为根节点。
- 利用哈希表 O(1) 查询当根节点在中序遍历中下标为 index。从 in_left 到 index - 1 属于左子树，从 index + 1 到 in_right 属于右子树。
- 根据后序遍历逻辑，递归创建右子树 helper(index + 1, in_right) 和左子树 helper(in_left, index - 1)。注意这里有需要先创建右子树，再创建左子树的依赖关系。可以理解为在后序遍历的数组中整个数组是先存储左子树的节点，再存储右子树的节点，最后存储根节点，如果按每次选择「后序遍历的最后一个节点」为根节点，则先被构造出来的应该为右子树。
- 返回根节点 root。

class Solution {
    int post_idx;
    unordered_map<int, int> idx_map;
public:
    TreeNode* helper(int in_left, int in_right, vector<int>& inorder, vector<int>& postorder){
        // 如果这里没有节点构造二叉树了，就结束
        if (in_left > in_right) {
            return nullptr;
        }

        // 选择 post_idx 位置的元素作为当前子树根节点
        int root_val = postorder[post_idx];
        TreeNode* root = new TreeNode(root_val);

        // 根据 root 所在位置分成左右两棵子树
        int index = idx_map[root_val];

        // 下标减一
        post_idx--;
        // 构造右子树
        root->right = helper(index + 1, in_right, inorder, postorder);
        // 构造左子树
        root->left = helper(in_left, index - 1, inorder, postorder);
        return root;
    }
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        // 从后序遍历的最后一个元素开始
        post_idx = (int)postorder.size() - 1;

        // 建立（元素，下标）键值对的哈希表
        int idx = 0;
        for (auto& val : inorder) {
            idx_map[val] = idx++;
        }
        return helper(0, (int)inorder.size() - 1, inorder, postorder);
    }
};

力扣1631.最小体力消耗路径

原题链接

你准备参加一场远足活动。给你一个二维 rows x columns 的地图 heights ，其中 heights[row][col] 表示格子 (row, col) 的高度。一开始你在最左上角的格子 (0, 0) ，且你希望去最右下角的格子 (rows-1, columns-1) （注意下标从 0 开始编号）。你每次可以往上，下，左，右四个方向之一移动，你想要找到耗费体力最小的一条路径。

一条路径耗费的 体力值 是路径上相邻格子之间 高度差绝对值 的 最大值 决定的。

请你返回从左上角走到右下角的最小 体力消耗值 。

示例 1：

输入：heights = [[1,2,2],[3,8,2],[5,3,5]]
输出：2
解释：路径 [1,3,5,3,5] 连续格子的差值绝对值最大为 2 。
这条路径比路径 [1,2,2,2,5] 更优，因为另一条路径差值最大值为 3 。

示例 2：

输入：heights = [[1,2,3],[3,8,4],[5,3,5]]
输出：1
解释：路径 [1,2,3,4,5] 的相邻格子差值绝对值最大为 1 ，比路径 [1,3,5,3,5] 更优。

示例 3：

输入：heights = [[1,2,1,1,1],[1,2,1,2,1],[1,2,1,2,1],[1,2,1,2,1],[1,1,1,2,1]]
输出：0
解释：上图所示路径不需要消耗任何体力。

提示：

rows == heights.length
columns == heights[i].length
1 <= rows, columns <= 100
1 <= heights[i][j] <= 106

大佬题解：

本题实际上即为：

将每个格子抽象成图中的一个点；
将每两个相邻的格子之间连接一条边，长度为这两个格子本身权值的差的绝对值；
需要找到一条从左上角到右下角的「最短路径」，其中路径的长度定义为路径上所有边的权值的最大值。

这也是一道比较经典的题目了，常用的方法有如下几种：

「二分答案」：我们可以对最短路径的长度进行二分。当我们二分枚举到的长度为 xxx 时，我们只保留所有长度 ≤xx≤x 的边。随后从左上角开始进行搜索（深度优先搜索、广度优先搜索）均可，只需要判断是否能够到达右下角即可。如果能够到达右下角，我们就可以减小 xxx 的值，反之增大 xxx 的值。
「并查集」：我们可以将所有边按照长度进行排序并依次添加进并查集，直到左上角和右下角连通为止。
「最短路」：我们可以使用任一单源最短路径的算法（例如 Dijkstra 算法），只需要在维护当前路径长度时，将其修改为题目中的定义即可。

方法一：二分答案

//方法一：二分法,找到最小的高度差，使得存在所有高度差都小于等于这个值的路连通(0,0) 和(n-1,n-1)

class Solution {
public:
    static constexpr int dirs[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

    int minimumEffortPath(vector<vector<int>>& heights)
    {
        int r = heights.size();
        int l = heights[0].size();

        int ans = 0;
        int left = 0;
        int right = 999999;
        while(left <= right)
        {
            int mid = (left+right)/2;
            vector<bool> visited(r*l, false);
            queue<pair<int, int>> q;
            q.emplace(0, 0);
            visited[0] = true;
            while(!q.empty())
            {
                auto [curx, cury] = q.front();
                q.pop();

                for(int i = 0; i<4; i++)
                {
                    int nx = curx+dirs[i][0];
                    int ny = cury+dirs[i][1];
                    if(nx >= 0 && nx<r && ny>=0 && ny<l &&!visited[nx*l+ny] && abs(heights[nx][ny]-heights[curx][cury])<=mid )
                    {
                        visited[nx*l+ny] = true;
                        q.emplace(nx, ny);
                    }
                }
            }

            if(visited[r*l - 1])
            {
                ans = mid;
                right = mid-1;
            }
            else
            {
                left = mid+1;
            }
        }

        return ans;
    }
};

方法二：并查集+sort排序

//方法二：并查集
class UnionFind{
public:
    vector<int> father;
    vector<int> deep;
    int size;

    UnionFind(int _n): size(_n), father(_n), deep(_n, 1){
        iota(father.begin(), father.end(), 0);
    }

    int findfa(int x)
    {
        return father[x] == x ? x : findfa(father[x]);
    }

    void merge(int a, int b)
    {
        int fa = findfa(a), fb = findfa(b);
        if(fa == fb) return;
        if(deep[fa] <= deep[fb])
            father[fa] = fb;
        else
            father[fb] = fa;

        if(deep[fa] == deep[fb])
            deep[fb]++;
        
        size--;
    }

    bool connected(int a, int b)
    {
        int fa = findfa(a);
        int fb = findfa(b);
        return fa == fb;
    }

};

struct Edge
{
    int x, y, z;
    Edge(int _x, int _y, int _z):x(_x), y(_y), z(_z){}
    bool operator< (const Edge& that) const
    {
        return z<that.z;
    }
};

//并查集的思路：找到将最小的东西连起来看能能不能连通

class Solution {
public:
    int r, l;
    static constexpr int dirs[4][2] = {{1,0}, {-1,0}, {0,1}, {0,-1}};
    int minimumEffortPath(vector<vector<int>>& heights)
    {
        r = heights.size();
        l = heights[0].size();
        vector<Edge> edges;
        for(int i = 0; i<r; i++)
        {
            for(int j = 0; j<l; j++)
            {
                int id = i*l + j;
                if(i>0)
                {
                    edges.emplace_back(id-l, id, abs(heights[i][j]-heights[i-1][j]));
                }
                if(j>0)
                {
                    edges.emplace_back(id-1, id, abs(heights[i][j]-heights[i][j-1]));
                }
            }
        }

        sort(edges.begin(), edges.end());
        UnionFind uf(r*l);
        for(const auto& e:edges)
        {
            uf.merge(e.x, e.y);
            if(uf.connected(0, r*l-1))
            {
                return e.z;
            }
        }
        return 0;
    }
};

方法三：最短路：优先队列

//方法三：Dijkstra算法：优先队列：比较消耗体力的最大值

//设计边类
struct Dot{
    int x, y, z;//存储目标点的 x,y 坐标，以及到达z的体力值
    Dot(int _x, int _y, int _z): x(_x), y(_y), z(_z){}
    bool operator<(const Dot& that) const{
        return z>that.z;//长度越长，优先级越小
    }
};

class Solution {
public:
//方向数组
    static constexpr int dirs[4][2] = {{1,0}, {-1,0}, {0,1}, {0,-1}};

    int minimumEffortPath(vector<vector<int>>& heights) {
        int r = heights.size();
        int l = heights[0].size();

        priority_queue<Dot> q;//优先队列，存储点及其与(0,0)点的最小消耗体力值
        //优先队列保证消耗体力小的放置在前面，当一个点放了两次，会选择最小的体力消耗的那个点进行pop
        vector<int> dist(r*l, INT_MAX);//存储最小消耗体力值
        vector<int> visited(r*l, 0); //存储是否访问过
        //初始化
        dist[0] = 0;
        q.emplace(0,0,0);
        while(!q.empty()){
            auto [x,y,z] = q.top();
            q.pop();
            if(visited[x*l+y]) continue; //在此之前有更小体力消耗的点，已经被访问了
            visited[x*l+y] = 1; //防止重复访问，导致陷入死循环
            dist[x*l+y] = z;
            for(int i = 0; i<4; i++){
                int nx = x+dirs[i][0];
                int ny = y+dirs[i][1];
                if(nx>=0 && nx<r && ny>=0 && ny<l && !visited[nx*l+ny]){
                    q.emplace(nx, ny, max(z, abs(heights[x][y] - heights[nx][ny])));
                }
            }
        }
        return dist[r*l-1];
    }
};

卡布叻_米菲的世界

树

叉树理论基础篇

二叉树的种类

满二叉树

完全二叉树

二叉搜索树

平衡二叉搜索树

二叉树的存储方式

二叉树的遍历方式

二叉树的定义

二叉树的遍历

递归遍历

迭代遍历

先序遍历

中序遍历

后序遍历

迭代遍历的统一代码

中序遍历

前序遍历

层序遍历 | 广度优先搜索

二叉搜索树中的搜索

例题

二叉树的最大深度

二叉树的最近公共祖先

二叉搜索树的最近公共祖先

二叉搜索树中的插入操作

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