Leetcode hot 100之二叉树

目录

 (反)序列化二叉树(str<->tree):前序

前序遍历(迭代)/路径

stack.length

入栈:中右左

出栈:中左右

中序遍历(迭代)

cur||stack.length

后序遍历(迭代)

和前序遍历不同:

入栈:中左右

出栈:中右左

reverse出栈:左右中

层序遍历(BFS):可求树的深/高度

找树左下角的值:最后一行的最左边的值

判断完全二叉树

queue.length

flag = false; //是否遇到空节点

判断平衡二叉树

递归Math.max(getMaxDepth(root.left)+1,getMaxDepth(root.right)+1)

判断对称二叉树

递归deep(left.left, right.right) && deep(left.right, right.left)

翻转/生成镜像二叉树

递归交换左右

两节点的最近公共祖先

递归后序遍历

构造二叉树

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

最大二叉树:二叉树的根是数组中的最大元素(递归定义)

二叉搜索树:左<根<右(按中序遍历有序的树)

删除二叉搜索树中的节点

修剪二叉搜索树

有序数组转换为平衡二叉搜索树

left, right比arr.slice高效

Math.floor(left + (right - left) / 2)

最值、差值->有序数组的差值、最值

二叉搜索树的最小绝对差

二叉搜索树转换为累加树


 (反)序列化二叉树(str<->tree):前序

function TreeNode(x) {this.val = x;this.left = null;this.right = null;
}
//反序列化二叉树:tree->str 把一棵二叉树按照某种遍历方式的结果以某种格式保存为字符串
function Serialize(pRoot, arr = []) {if (!pRoot) {arr.push("#");return arr;} else {arr.push(pRoot.val);//注意是val。而不是rootSerialize(pRoot.left, arr);Serialize(pRoot.right, arr);}return arr;
}
//序列化二叉树:str->tree 根据字符串结果str,重构二叉树
function Deserialize(s) {//转换为数组let arr = Array.isArray(s) ? s : s.split("");//取出vallet a = arr.shift();//构建二叉树结点let node = null;if (typeof a === "number") {//还有可能等于#node = new TreeNode(a);node.left = Deserialize(arr);node.right = Deserialize(arr);}return node;
}
module.exports = {Serialize: Serialize,Deserialize: Deserialize,
};

前序遍历(迭代)/路径

stack.length

入栈:中右左

出栈:中左右

/*** 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 preorderTraversal = function(root) {let stack=[]let res = []let cur = null;if(!root) return res;root&&stack.push(root)while(stack.length){cur = stack.pop()res.push(cur.val)cur.right&&stack.push(cur.right)cur.left&&stack.push(cur.left)}return res
};

中序遍历(迭代)

cur||stack.length

指针的遍历来帮助访问节点,栈则用来处理节点上的元素

/*** 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) {let stack = []let res = []let cur = rootwhile(cur||stack.length){if(cur){stack.push(cur)cur = cur.left} else {cur = stack.pop()res.push(cur.val)cur = cur.right}}return res
};

后序遍历(迭代)

和前序遍历不同:

入栈:中左右

出栈:中右左

reverse出栈:左右中

/*** 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) {let stack = []let res = []let cur = rootif(!root) return resstack.push(root)while(stack.length){cur = stack.pop()res.push(cur.val)cur.left&&stack.push(cur.left)cur.right&&stack.push(cur.right)}return res.reverse()};

层序遍历(BFS):可求树的深/高度

层序遍历,相似 广度优先搜索

  1. 初始设置一个空队根结点入队
  2. 队首结点出队,其左右孩子 依次 入队
  3. 队空,说明 所有结点 已处理完,结束遍历;否则(2)
/** function TreeNode(x) {*   this.val = x;*   this.left = null;*   this.right = null;* }*//**** @param root TreeNode类* @return int整型二维数组*/
function levelOrder(root) {// write code hereif (root == null) {return [];}const arr = [];const queue = [];queue.push(root);while (queue.length) {const preSize = queue.length;const floor = [];//当前层for (let i = 0; i < preSize; ++i) {const v = queue.shift();floor.push(v.val);v.left&&queue.push(v.left);v.right&&queue.push(v.right);}arr.push(floor);}return arr;//[[1],[2,3]]
}
module.exports = {levelOrder: levelOrder,
};

找树左下角的值:最后一行的最左边的值

判断完全二叉树

queue.length

flag = false; //是否遇到空节点

完全二叉树:叶子节点只能出现在最下层和次下层,且最下层的叶子节点集中在树的左部。

/** function TreeNode(x) {*   this.val = x;*   this.left = null;*   this.right = null;* }*/
/*** 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可*** @param root TreeNode类* @return bool布尔型*/
function isCompleteTree(root) {// write code hereif (root == null) return true;const queue = [];queue.push(root);let flag = false; //是否遇到空节点while (queue.length) {const node = queue.shift();if (node == null) {//如果遇到某个节点为空,进行标记,代表到了完全二叉树的最下层flag = true;continue;}if (flag == true) {//若是后续还有访问,则说明提前出现了叶子节点,不符合完全二叉树的性质。return false;}queue.push(node.left);queue.push(node.right);}return true;
}
module.exports = {isCompleteTree: isCompleteTree,
};

判断平衡二叉树

平衡二叉树是左子树的高度与右子树的高度差的绝对值小于等于1,同样左子树是平衡二叉树,右子树为平衡二叉树。

递归Math.max(getMaxDepth(root.left)+1,getMaxDepth(root.right)+1)

/* function TreeNode(x) {this.val = x;this.left = null;this.right = null;
} */
function IsBalanced_Solution(pRoot)
{if(!pRoot) return true;// write code herereturn (Math.abs(getMaxDepth(pRoot.left) - getMaxDepth(pRoot.right)) <=1) && IsBalanced_Solution(pRoot.left) && IsBalanced_Solution(pRoot.right)
}function getMaxDepth(root) {if(!root) return 0;return Math.max(getMaxDepth(root.left)+1,getMaxDepth(root.right)+1)
}
module.exports = {IsBalanced_Solution : IsBalanced_Solution
};

判断对称二叉树

递归deep(left.left, right.right) && deep(left.right, right.left)

/* function TreeNode(x) {this.val = x;this.left = null;this.right = null;
} */
let flag = true;
function deep(left, right) {if (!left && !right) return true; //可以两个都为空if (!right||!left|| left.val !== right.val) {//只有一个为空或者节点值不同,必定不对称return false;}return deep(left.left, right.right) && deep(left.right, right.left); //每层对应的节点进入递归比较
}
function isSymmetrical(pRoot) {return deep(pRoot, pRoot);
}
module.exports = {isSymmetrical: isSymmetrical,
};

翻转/生成镜像二叉树

递归交换左右

先序遍历

/** function TreeNode(x) {*   this.val = x;*   this.left = null;*   this.right = null;* }*/
/*** 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可** * @param pRoot TreeNode类 * @return TreeNode类*/
function Mirror( pRoot ) {function traversal(root){if(root===null) return ;//交换左右孩子let temp = root.left;root.left = root.right;root.right = temp;traversal(root.left);traversal(root.right);return root;}return traversal(pRoot);// write code here
}
module.exports = {Mirror : Mirror
};

两节点的最近公共祖先

 如果从两个节点往上找,每个节点都往上走,一直走到根节点,那么根节点到这两个节点的连线肯定有相交的地方,

如果从上往下走,那么最后一次相交的节点就是他们的最近公共祖先节点。

递归后序遍历

/** function TreeNode(x) {*   this.val = x;*   this.left = null;*   this.right = null;* }*//**** @param root TreeNode类* @param o1 int整型* @param o2 int整型* @return int整型*/
function dfs(root, o1, o2) {if (root == null || root.val == o1 || root.val == o2) {return root;}//递归遍历左子树let left = dfs(root.left, o1, o2);//递归遍历右子树let right = dfs(root.right, o1, o2);//如果left、right都不为空,那么代表o1、o2在root的两侧,所以root为他们的公共祖先if (left && right) return root;//如果left、right有一个为空,那么就返回不为空的那一个return left != null ? left : right;
}

构造二叉树

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

//前
var buildTree = function(preorder, inorder) {if (!preorder.length) return null;const rootVal = preorder.shift(); // 从前序遍历的数组中获取中间节点的值, 即数组第一个值const index = inorder.indexOf(rootVal); // 获取中间节点在中序遍历中的下标const root = new TreeNode(rootVal); // 创建中间节点root.left = buildTree(preorder.slice(0, index), inorder.slice(0, index)); // 创建左节点root.right = buildTree(preorder.slice(index), inorder.slice(index + 1)); // 创建右节点return root;
};
//后
var buildTree = function(inorder, postorder) {if (!inorder.length) return null;const rootVal = postorder.pop(); // 从后序遍历的数组中获取中间节点的值, 即数组最后一个值let rootIndex = inorder.indexOf(rootVal); // 获取中间节点在中序遍历中的下标const root = new TreeNode(rootVal); // 创建中间节点root.left = buildTree(inorder.slice(0, rootIndex), postorder.slice(0, rootIndex)); // 创建左节点root.right = buildTree(inorder.slice(rootIndex + 1), postorder.slice(rootIndex)); // 创建右节点return root;
};

最大二叉树:二叉树的根是数组中的最大元素(递归定义)

var constructMaximumBinaryTree = function (nums) {const BuildTree = (arr, left, right) => {if (left > right)return null;let maxValue = -1;let maxIndex = -1;for (let i = left; i <= right; ++i) {if (arr[i] > maxValue) {maxValue = arr[i];maxIndex = i;}}let root = new TreeNode(maxValue);root.left = BuildTree(arr, left, maxIndex - 1);root.right = BuildTree(arr, maxIndex + 1, right);return root;}let root = BuildTree(nums, 0, nums.length - 1);return root;
};

二叉搜索树:左<根<右(按中序遍历有序的树)

删除二叉搜索树中的节点

/*** 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* @param {number} key* @return {TreeNode}*/
var deleteNode = function(root, key) {if (!root) return null;if (key > root.val) {root.right = deleteNode(root.right, key);return root;} else if (key < root.val) {root.left = deleteNode(root.left, key);return root;} else {// 场景1: 该节点是叶节点if (!root.left && !root.right) {return null}// 场景2: 有一个孩子节点不存在if (root.left && !root.right) {return root.left;} else if (root.right && !root.left) {return root.right;}// 场景3: 左右节点都存在const rightNode = root.right;// 获取最小值节点const minNode = getMinNode(rightNode);// 将待删除节点的值替换为最小值节点值root.val = minNode.val;// 删除最小值节点root.right = deleteNode(root.right, minNode.val);return root;}
};
function getMinNode(root) {while (root.left) {root = root.left;}return root;
}

修剪二叉搜索树

修剪二叉搜索树,使得所有节点的值在[L, R]中 (R>=L) 

var trimBST = function (root,low,high) {if(root === null) {return null;}if(root.val < low) {let right = trimBST(root.right, low, high);return right;}if(root.val > high) {let left = trimBST(root.left, low, high);return left;}root.left = trimBST(root.left, low, high);root.right = trimBST(root.right, low, high);return root;}

有序数组转换为平衡二叉搜索树

left, right比arr.slice高效

Math.floor(left + (right - left) / 2)

var sortedArrayToBST = function (nums) {const buildTree = (Arr, left, right) => {if (left > right)return null;let mid = Math.floor(left + (right - left) / 2);let root = new TreeNode(Arr[mid]);root.left = buildTree(Arr, left, mid - 1);root.right = buildTree(Arr, mid + 1, right);return root;}return buildTree(nums, 0, nums.length - 1);
};

最值、差值->有序数组的差值、最值

二叉搜索树的最小绝对差

二叉搜索树转换为累加树

一个有序数组[2, 5, 13],求从后到前的累加数组,也就是[20, 18, 13]

累加的顺序是右中左,所以我们需要反中序遍历这个二叉树,然后顺序累加

’东哥带你刷二叉树(思路篇) | labuladong 的算法笔记

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/152094.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

计算机视觉处理的开源框架

计算机视觉是一门涉及图像和视频分析的领域&#xff0c;有许多开源的框架和库可用于构建计算机视觉应用程序。以下是一些常见的计算机视觉开源框架及其特点&#xff0c;希望对大家有所帮助。北京木奇移动技术有限公司&#xff0c;专业的软件外包开发公司&#xff0c;欢迎交流合…

一盏茶的功夫帮你彻底搞懂JavaScript异步编程从回调地狱到async/await

&#x1f3ac; 江城开朗的豌豆&#xff1a;个人主页 &#x1f525; 个人专栏 :《 VUE 》 《 javaScript 》 ⛺️ 生活的理想&#xff0c;就是为了理想的生活 ! 目录 &#x1f4d8; 1. 引言 &#x1f4d8; 2. 使用方法 &#x1f4d8; 3. 实现原理 &#x1f4d8; 4. 写到最后…

Android 自定义PopupWindow,实现下拉框

1、效果图 2、前言 1、页面由 MagicIndicator ViewPager2 Fragment 实现&#xff1b; 2、下拉框是基于WindowManager实现&#xff1b; 3、我使用PopupWindow实现下拉框时&#xff0c;发现一个问题&#xff0c;PopupWindow 在窗口显示的情况下&#xff0c;无法直接从外部修…

(c语言进阶)指针的进阶

一.字符指针 1.一般应用 &#xff08;1&#xff09;%c的应用 &#xff08;2&#xff09;%s的应用 字符指针没有权限通过解引用去改变指针指向的值 2.笔试题 题目&#xff1a;判断输出结果 int main() { const char* p1 "abcdef"; const char* p2 "…

无法向会话状态服务器发出会话状态请求。请确保 ASP.NET State Service (ASP.NET 状态服务)已启动,并且客户端端口与服务器端口相同

“/”应用程序中的服务器错误。 无法向会话状态服务器发出会话状态请求。请确保 ASP.NET State Service (ASP.NET 状态服务)已启动&#xff0c;并且客户端端口与服务器端口相同。如果服务器位于远程计算机上&#xff0c;请检查 HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\Se…

【云备份】

文章目录 [toc] 1 :peach:云备份的认识:peach:1.1 :apple:功能了解:apple:1.2 :apple:实现目标:apple:1.3 :apple:服务端程序负责功能:apple:1.4 :apple:服务端功能模块划分:apple:1.5 :apple:客户端程序负责功能:apple:1.6 :apple:客户端功能模块划分:apple: 2 :peach:环境搭建…

[VC++]圆形进度条

[VC]圆形进度条 源码开发环境&#xff1a;VC6.0 WIN10 64位下编译通过利用绘制饼图的原理&#xff0c;来制作的圆形进度条&#xff0c;可以显示百分比。软件运行截图如下&#xff1a; 附件源码下载(点击下载&#xff09;

基于ensp的园区网络搭建综合实验

目录 &#x1f552; 1. 技术介绍&#x1f552; 2. 需求分析&#x1f558; 2.1 项目背景和需求&#x1f558; 2.2 项目需求分析 &#x1f552; 3. 网络结构设计&#x1f552; 4. 网络拓扑规划&#x1f552; 5. 网络设备基本配置&#x1f558; 5.1 规划VLAN&#x1f558; 5.2 MST…

【RK3588】YOLO V5在瑞芯微板子上部署问题记录汇总

YOLO V5训练模型部署到瑞芯微的板子上面&#xff0c;官方是有给出案例和转过详情的。并且也提供了Python版本的推理代码&#xff0c;以及C语言的代码。 但是&#xff0c;对于转换过程中的细节&#xff0c;哪些需要改&#xff1f;怎么改&#xff1f;如何改&#xff0c;和为什么…

Java中树形菜单的实现方式(超全详解!)

前言 这篇文中&#xff0c;我一共会用两种方式来实现目录树的数据结构&#xff0c;两种写法逻辑是一样的&#xff0c;只是一种适合新手理解&#xff0c;一种看着简单明了但是对于小白不是很好理解。在这里我会很详细的讲解每一步代码&#xff0c;主要是方便新人看懂&#xff0…

typescript: Builder Pattern

/*** file: CarBuilderts.ts* TypeScript 实体类 Model* Builder Pattern* 生成器是一种创建型设计模式&#xff0c; 使你能够分步骤创建复杂对象。* https://stackoverflow.com/questions/12827266/get-and-set-in-typescript* https://github.com/Microsoft/TypeScript/wiki/…

4.Docker 搭建 redis6

1.下载redis docker pull redis:6.2.62.创建需要挂载的宿主机文件夹 mkdir -p /data/redis/conf mkdir -p /data/redis/data3.配置redis 切换到/data/redis/conf文件夹下&#xff0c;创建redis.conf,复制redis.conf配置文件内容到redis.conf文件中&#xff0c;然后按下键盘 …

黑豹程序员-架构师学习路线图-百科:AJAX

文章目录 1、什么是AJAX2、发展历史3、工作原理4、一句话概括 1、什么是AJAX Ajax即Asynchronous&#xff08;呃森可乐思&#xff09; Javascript And XML&#xff08;异步JavaScript和XML&#xff09; 在 2005年被Jesse James Garrett&#xff08;杰西詹姆斯加勒特&#xff09…

GD32F103x 定时器

1. 定时器的基本介绍 STM32的定时器主要分为三种&#xff1a;高级定时器、通用定时器、基本定时器。 即&#xff1a;高级定时器具有捕获/比较通道和互补输出&#xff0c;死区时间&#xff0c;通用定时器只有捕获/比较通道&#xff0c;基本定时器没有以上两者。 1. 基本定时…

网络安全:六种常见的网络攻击手段

1、什么是VPN服务&#xff1f; 虚拟专用网络&#xff08;或VPN&#xff09;是您的设备与另一台计算机之间通过互联网的安全连接。VPN服务可用于在离开办公室时安全地访问工作计算机系统。但它们也常用于规避政府审查制度&#xff0c;或者在电影流媒体网站上阻止位置封锁&#…

【React】深入理解React组件状态State

目录 一、何为State二、如何定义State三、如何判断是否为State四、如何正确使用State1、用setState修改State2、State的更新是异步的①、代码示例 3、State更新会被合并①、组件状态例子②、当只需要修改状态title时&#xff0c;只需要将修改后的title传给setState③、React会合…

Windows安装Node.js

1、Node.js介绍 ①、Node.js简介 Node.js是一个开源的、跨平台的JavaScript运行环境&#xff0c;它允许开发者使用JavaScript语言来构建高性能的网络应用程序和服务器端应用。Node.js的核心特点包括&#xff1a; 1. 事件驱动: Node.js采用了事件驱动的编程模型&#xff0c;通…

力扣 -- 647. 回文子串

解题步骤&#xff1a; 参考代码&#xff1a; class Solution { public:int countSubstrings(string s) {int ns.size();vector<vector<bool>> dp(n,vector<bool>(n));//无需初始化int ret0;//一定要从下往上填写每一行for(int in-1;i>0;i--){//每一行的i…

jvm--对象实例化及直接内存

文章目录 1. 创建对象2. 对象内存布局3. 对象的访问定位4. 直接内存&#xff08;Direct Memory&#xff09; 1. 创建对象 创建对象的方式&#xff1a; new最常见的方式、Xxx 的静态方法&#xff08;单例模式&#xff09;&#xff0c;XxxBuilder/XxxFactory 的静态方法Class 的…

CVE-2023-36845:Juniper Networks Junos OS EX远程命令执行漏洞

Juniper Networks Junos OS EX远程命令执行漏洞(CVE-2023-36845) 复现 0x01 前言 免责声明&#xff1a;请勿利用文章内的相关技术从事非法测试&#xff0c;由于传播、利用此文所提供的信息或者工具而造成的任何直接或者间接的后果及损失&#xff0c;均由使用者本人负责&#…