2023-10-11

Source

Edit

History

LRU 缓存

一、题目

请你设计并实现一个满足 LRU (最近最少使用) 缓存约束的数据结构。
实现 LRUCache 类：
LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存
int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该逐出最久未使用的关键字。
函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

Leetcode：https://leetcode.cn/problems/lru-cache

二、分析

本题使用双向链表+哈希表的方式，可以完成如上的要求。

当 get 的时候，我们从哈希表中查找，如果找不到，直接返回 -1。如果找到了，将此节点从双向链表中移动到最前端，并返回

当 put 的时候，先从哈希表中查找，如果找到了，则更改值。如果找不到，创建节点，并将其插入到哈希表，然后放在双向链表的前端。最后检测双向链表的容量，容量超了，就删除尾节点。

算法刷题目二叉树

2023-10-11

Source

Edit

History

二叉树节点间的最大距离

一、题目

二叉树上的两个节点，求这两个节点之间的最大距离

二、思路

两个节点之间的距离不一定要经过一颗二叉树的根节点。我们以递归的思路来思考。既然是求二叉树的任意两个节点。那我们以二叉树的一个节点为例，这个节点组成的树；我们可以分成三种情况：

这个节点的左子树，求得这个节点左子树上最大的距离

算法刷题目二叉树

2023-10-11

Source

Edit

History

二叉树的最近公共祖先

一、题目

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

最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

进阶问题：如果查询两个节点的最近公共祖先的操作十分频繁，想法让单条查询的时间减少。

leetcode：https://leetcode.cn/problems/er-cha-shu-de-zui-jin-gong-gong-zu-xian-lcof/

二、思路

给定的两个节点一个为 p，一个为 q
当前节点记为 cur，他的左子树记为 left，他的右子树记为 right
我们需要 left 和 right 的值来做逻辑判断，因此很适合用后序遍历。

算法刷题目二叉树

2023-10-11

Source

Edit

History

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

一、题目

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

Leetcode：https://leetcode.cn/problems/construct-binary-tree-from-inorder-and-postorder-traversal/description/

二、分析

后序遍历是左右根，所以我们很容易确定根节点。

通过这个根节点，加上中序遍历序列。即可划分出左右子树。

注意可以通过哈希表缓存中序遍历的结果，这样可以加快查找

算法刷题目二叉树

2023-10-11

Source

Edit

History

判断二叉树是否为平衡二叉树

一、题目

输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。

leetcode：https://leetcode.cn/problems/ping-heng-er-cha-shu-lcof/

二、思路

判断一颗二叉树是否为平衡树，那就判断这颗二叉树的左子树是否为平衡树、右子树是否为平衡树。并且在判断子树的时候记录子树的高度即可。

用一个变量来记录是否为平衡二叉树，如果在判断的中间过程，发现不是平衡的了，马上置为 false，保证这个 bool 变量是个指针或引用。左右子树都是平衡的，那就返回左右子树的高度，看当前节点所代表的树是否平衡。

三、code

#include <iostream>
#include <algorithm>

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;

    explicit TreeNode(int val) : val(val), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    bool isBalanced(TreeNode* root) {
        bool res = true;
        get_hight(root, 1, res);
        return res;
    }

private:
    int get_hight(TreeNode* node, int level, bool& res) {
        if (node == nullptr) {
            return level;
        }
        int left_high = get_hight(node->left, level+1, res);
        if (!res) {
            return level;
        }
        int right_high = get_hight(node->right, level+1, res);
        if (!res) {
            return level;
        }
        if (std::abs(left_high - right_high) > 1) {
            res = false;
        }
        return std::max(left_high, right_high);
    }
};

算法刷题目二叉树

2023-10-11

Source

Edit

History

二叉树的前中后序遍历

二叉树的前序、中序、后序遍历是我们学习二叉树的第一节课。那么如何写出易于理解的代码呢？以下的思路是我最近再次思考的结果。

二叉树的前中后序的递归遍历很简单，如下

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;

    explicit TreeNode(int val) : val(val), left(nullptr), right(nullptr) {}
};

void pre_order_recur(TreeNode* root) {
    if (root == nullptr) {
        return;
    }
    std::cout << root->val << " ";
    pre_order_recur(root->left);
    pre_order_recur(root->right);
}

// 左根右
void in_order_recur(TreeNode* root) {
    if (root == nullptr) {
        return;
    }
    in_order_recur(root->left);
    std::cout << root->val << " ";
    in_order_recur(root->right);
}

// 左右根
void post_order_recur(TreeNode* root) {
    if (root == nullptr) {
        return;
    }
    post_order_recur(root->left);
    post_order_recur(root->right);
    std::cout << root->val << " ";
}

那么我们就递归代码改造成非递归就可以解决问题。递归的本质是在系统栈上存储我们想要的数据，那么我们可以自己构造栈，将数据存储到我们自己的栈上。因此系统栈本身除了保存我们想要的数据外，还有其他比如寄存器指针、函数地址等等额外的数据，导致占用过多的内存空间。于是，我们的非递归代码的主要逻辑是找到需要保存的我们需要的数据。

算法刷题目二叉树

2023-10-11

Source

Edit

History

二叉树的层序遍历

一、题目

给你二叉树的根节点 root ，返回其节点值的 层序遍历 。（即逐层地，从左到右访问所有节点）

但是有一个条件，每一层输出一行。

Leetcode：https://leetcode.cn/problems/binary-tree-level-order-traversal/

二、思路

一般的层序遍历比较简单，只需要使用一个队列，但是现在加上一个条件，即每一层按行打印。因此我们就需要知道每一行的最右边的节点，然后做换行操作。那么如何得知每一行最右边的节点呢？首先我们知道 root 节点，即根节点为第一层的最右节点。使用两个变量，一个记录当前层的最右节点，记为 last；另一个记录下一层的最右节点，记为 nlast。而我们在遍历每个节点时，都去判断当前节点是否为当前层的最右节点即可。如果已经遍历到当前层的最右节点了，那么下一层的最右节点其实也已经被赋值了。此时将下一层的最右节点 nlast 赋给 last 即可。

三、code

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;

    explicit TreeNode(int val) : val(val), left(nullptr), right(nullptr) {}
};

void level_recur(TreeNode* root) {
	if (root == nullptr) {
		return;
	}
	TreeNode* last = root;
	TreeNode* nlast = nullptr;
	std::queue<TreeNode*> qu;
	qu.push(root);
	int count = 1;
	std::cout << "level " << count << ": ";
	while (!qu.empty()) {
		TreeNode* node = qu.front();
		qu.pop();
		std::cout << node->val << " ";
		if (node->left) {
			qu.push(node->left);
			nlast = node->left;
		}
		if (node->right) {
			qu.push(node->right);
			nlast = node->right;
		}
		if (node == last && !qu.empty()) {
			std::cout << std::endl << "level " << count++ << ": ";
			last = nlast;
		}
	}
	std::cout << std::endl;
}

算法刷题目二叉树

2023-10-11

Source

Edit

History

二叉树中找节点的后继节点

一、题目

给一个二叉树，这个二叉树的节点结构中多了一个父亲节点。如下

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode* parent;

    explicit TreeNode(int val) : val(val), left(nullptr), right(nullptr) {}
};