数据结构
图论
最短路径
先走 深搜 构造无向图 然后从 start 节点开始走 广搜 寻找最短路径
二叉树
前序遍历
前序遍历是一种深度优先搜索的遍历方式, 遍历顺序为 根结点 -> 左子树 -> 右子树 的顺序
示例 1:
example 1
1
/ \
2 3
/ \ / \
4 5 6 7
遍历输出为 [1,2,4,5,3,6,7]示例 2:
example 2
1
/ \
2 3
/ \
4 5
/ \
6 7
遍历输出为 [1,2,4,6,7,5,3]递归
Js
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {number[]}
*/
function preOrder(root, queue=[]){
if(!root)return queue;
queue.push(root.val)
preOrder(root.left,queue);
preOrder(root.right,queue);
return queue;
}迭代
利用栈先进后出的性质 实现迭代方式遍历
先入栈右子树
Js
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {number[]}
*/
function preOrder(root){
if(!root)return [];
const ans = [];
const stack = [root];
while (stack.length) {
const top = stack.pop();
ans.push(top.val);
if (top.right) stack.push(top.right);
if (top.left) stack.push(top.left);
}
return ans;
}中序遍历
中序遍历是一种深度优先搜索的遍历方式, 遍历顺序为 左子树 -> 根结点 -> 右子树
示例 1:
example 1
1
/ \
2 3
/ \ / \
4 5 6 7
遍历输出为 [4,2,5,1,6,3,7]示例 2:
example 2
1
/ \
2 3
/ \
4 5
/ \
6 7
遍历输出为 [6,4,7,2,5,1,3]递归
Js
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {number[]}
*/
var inorderTraversal = function (root, ans = []) {
if (!root) return ans;
inorderTraversal(root.left, ans);
ans.push(root.val);
inorderTraversal(root.right, ans);
return ans;
};迭代
Js
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {number[]}
*/
var inorderTraversal = function (root) {
if (!root) return [];
const ans = [];
const stack = [];
let current = root;
while (current || stack.length) {
while (current) {
stack.push(current);
current = current.left;
}
const top = stack.pop();
ans.push(top.val);
current = top.right;
}
return ans;
};后序遍历
后序遍历是一种深度优先搜索的遍历方式, 遍历顺序为 左子树 -> 右子树 -> 根结点
示例 1:
example 1
1
/ \
2 3
/ \ / \
4 5 6 7
遍历输出为 [4,5,2,6,7,3,1]示例 2:
example 2
1
/ \
2 3
/ \
4 5
/ \
6 7
遍历输出为 [6,7,4,5,2,3,1]递归
Js
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {number[]}
*/
var postorderTraversal = function (root, ans = []) {
if (!root) return ans;
postorderTraversal(root.left, ans);
postorderTraversal(root.right, ans);
ans.push(root.val);
return ans;
};迭代
先按 根节点 -> 右子树 -> 左子树 顺序遍历
然后将结果 逆转
Js
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {number[]}
*/
var postorderTraversal = function (root) {
if (!root) return [];
const stack = [root];
const ans = [];
while (stack.length) {
const top = stack.pop();
ans.push(top.val);
if (top.left) stack.push(top.left);
if (top.right) stack.push(top.right);
}
return ans.reverse();
};层序遍历
层序遍历是一种广度优先搜索的遍历方式, 从根节点开始, 按层访问树的节点
示例 1:
example 1
1
/ \
2 3
/ \ / \
4 5 6 7
遍历输出为 [[1],[2,3],[4,5,6,7]]示例 2:
example 2
1
/ \
2 3
/ \
4 5
/ \
6 7
遍历输出为 [[1],[2,3],[4,5],[6,7]]迭代
Js
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {number[][]}
*/
var levelOrder = function (root) {
if (!root) return [];
let q = [root];
const ans = [];
while (q.length) {
const size = q.length;
let current = [];
ans.push([]);
for (let i = 0; i < size; i++) {
const head = q[i];
ans[ans.length-1].push(head.val);
if (head.left) current.push(head.left);
if (head.right) current.push(head.right);
}
q = current;
}
return ans;
};相关的一些题目
使用 BFS 找出最深一层的节点集合, 然后求和
使用 BFS 计算每一层的和, 然后排序
二叉搜索树
二叉搜索树（Binary Search Tree，BST）具有以下特性
- 节点左子树中所有节点都小于该节点的值
- 节点右子树中所有节点都大于该节点的值
- 左子树和右子树也分别是二叉搜索树
二叉搜索树 支持高效搜索、插入、删除操作
搜索操作的时间复杂度为 O(log n), n 是树中节点数量
示例 1:
example 1
8
/ \
6 10
/ \ / \
5 7 9 11二叉平衡树
二叉平衡树是一种特殊的二叉搜索树, 在最坏的情况下搜索时间复杂度也是 O(log n)
- 树中每个节点左子树跟右子树高度差不超过 1
- 左子树与右子树也分别是二叉平衡树
示例 1
example 1
8
/ \
6 10
/ \
5 7递归获取左右子树高度差做计算, 同时递归判断左右子树是否也是平衡树
Js/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } */ /** * @param {TreeNode} root * @return {boolean} */ var isBalanced = function (root) { if (!root) return true; return Math.abs(height(root.left) - height(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right) }; function height(root) { if (!root) return 0; return Math.max(height(root.left) + 1, height(root.right) + 1); }
树
数组
链表
双链表
构造双链表存储节点, 每新增一个新数添加到头部, 已存在则更新 value 以及移动到头部 构造 map 存储每个链表节点, 方便在 get 时直接取到对应链表节点, 然后做移动到头节点动作
算法
双指针
哈希表
n 数之和