[数据结构与算法]js实现二叉树

DFS 与 BFS

dfs 递归 本质通过栈结构
bfs 层序遍历 通过队列结构

function permute(nums) {let res = [];let cur = []; // 记录当前内容let visted = {}; //记录访问过的节点let len = nums.length;function dfs(nth) {//递归终止条件if (nth === len) {res.push([...cur]);return ;}//检查还有哪些数字可以使用for (let i = 0; i < len; i++) {if (!visted[i]) {//记录访问过的节点visted[i] = true;cur.push(nums[i]);//递归dfs(nth + 1);//回溯cur.pop();visted[i] = false;}}}dfs(0);return res;}
//广度优先搜索function bfs(root) {let queue = [];//观察的当前节点入队queue.push(root);//当队列还有元素说明还没有遍历完while (queue.length) {//头节点出队let cur = queue.shift();//访问头节点console.log(cur.val);if (cur.left) queue.push(cur.left);if (cur.right) queue.push(cur.right);}

全排列

46. 全排列 - 力扣（LeetCode）

组合问题

78. 子集 - 力扣（LeetCode）

77. 组合 - 力扣（LeetCode）

二叉树遍历

先序遍历的迭代

var preorderTraversal = function(root) {let stk=[]let res=[]stk.push(root)while(stk.length!=0){let node = stk.pop()if(node) res.push(node.val)if(node && node.right) stk.push(node.right)if(node && node.left) stk.push(node.left)}return res};

后序遍历 的迭代

var postorderTraversal = function(root) {//左 右 中let res = []let stk=[]stk.push(root)while(stk.length){let node = stk.pop()if(node) res.push(node.val)if(node && node.left) stk.push(node.left)if(node && node.right) stk.push(node.right)}res.reverse()return res};

中序遍历的迭代

var inorderTraversal = function(root) {//左中右let stk =[]let res =[]let cur=rootwhile(stk.length || cur){while(cur){stk.push(cur)cur=cur.left}cur = stk.pop()res.push(cur.val)cur=cur.right}return res;};

层序遍历

var levelOrder = function(root) {let queue=[] // 每一层的值let res=[]if(!root) return resqueue.push(root)while(queue.length){let cur=[] //记录当前层的节点let len = queue.lengthwhile(len!=0){len--;let node = queue.shift()if(node) cur.push(node.val)if(node && node.left) queue.push(node.left)if(node && node.right) queue.push(node.right)}res.push(cur)}return res;};

二叉树翻转

var invertTree = function(root) {function dfs(root){if(!root) return null;let left =dfs(root.left)let right = dfs(root.right)root.left = rightroot.right = leftreturn root}dfs(root)return root};

二叉搜索树 BST

搜索,插入

 function dfs(root,val){//节点为空,找到目标if(!root){return new TreeNode(val)}if(val > root.val){root.right =  dfs(root.right,val)}else{root.left = dfs(root.left,val)}return root}

删除

var deleteNode = function(root, key) {function leftMax(root) {while (root.right) {root = root.right;}return root;}function rightMin(root) {while (root.left) {root = root.left;}return root;}function dfs(root, key) {if (!root) return null;// 找到了，进行删除操作if (root.val === key) {// 删除的是叶子节点，直接删除if (!root.left &&!root.right) {return null;} else if (root.left) {// 存在左子树--找到左子树中的最大值let node = leftMax(root.left);root.val = node.val;// 删除 noderoot.left = dfs(root.left, node.val);} else {// 存在右子树 -- 找到右子树的最小值let node = rightMin(root.right);root.val = node.val;// 删除 noderoot.right = dfs(root.right, node.val);}} else if (root.val > key) {root.left = dfs(root.left, key);} else {root.right = dfs(root.right, key);}return root;}return dfs(root, key);};

108. 将有序数组转换为二叉搜索树 - 力扣（LeetCode）

98. 验证二叉搜索树 - 力扣（LeetCode）

平衡二叉树 AVL

特殊的二叉搜索树
任意节点的左右子树绝对值不超过1

判定

var isBalanced = function(root) {let res = true;function dfs(root){if(!root) return 0;let left = dfs(root.left)let right = dfs(root.right)if(Math.abs(left-right)>1){res = false}let height = left > right ? left :rightreturn height+1;}dfs(root)return res;};

构造

1382. 将二叉搜索树变平衡 - 力扣（LeetCode）

特殊二叉树-堆结构

完全二叉树

每一层的节点数,都到达了当前层所能到达的最大值
从左到右,不存在跳序排列

索引规律
对索引为n的节点,

1. 父节点:(n-1)/2
2. 左孩子:2*n+1
3. 右孩子:2*n+2

堆是特殊的完全二叉树,分为大顶堆,小顶堆

删除—取出堆顶元素

以大顶堆为例,
不断向下对比交换的过程

// 入参是堆元素在数组里的索引范围，low表示下界，high表示上界
function downHeap(low, high) {// 初始化 i 为当前结点，j 为当前结点的左孩子let i=low,j=i*2+1 // 当 j 不超过上界时，重复向下对比+交换的操作while(j <= high) {// 如果右孩子比左孩子更大，则用右孩子和根结点比较if(j+1 <= high && heap[j+1] > heap[j]) {j = j+1}// 若当前结点比孩子结点小，则交换两者的位置，把较大的结点“拱上去”if(heap[i] < heap[j]) {// 交换位置const temp = heap[j]  heap[j] = heap[i]  heap[i] = temp// i 更新为被交换的孩子结点的索引i=j  // j 更新为孩子结点的左孩子的索引j=j*2+1} else {break}}
}

插入—往堆里面追加元素

首先放入堆的最后一个位置
不断向上比较交换的过程

// 入参是堆元素在数组里的索引范围，low表示下界，high表示上界
function upHeap(low, high) {// 初始化 i（当前结点索引）为上界let i = high  // 初始化 j 为 i 的父结点let j = Math.floor((i-1)/2)  // 当 j 不逾越下界时，重复向上对比+交换的过程while(j>=low)  {// 若当前结点比父结点大if(heap[j]<heap[i]) {// 交换当前结点与父结点，保持父结点是较大的一个const temp = heap[j] heap[j] = heap[i]  heap[i] = temp// i更新为被交换父结点的位置i=j   // j更新为父结点的父结点j=Math.floor((i-1)/2)  } else {break}}
}

优先队列

LCR 076. 数组中的第 K 个最大元素 - 力扣（LeetCode）