1.二叉树文章目录1.二叉树94. 二叉树的中序遍历方法一：c方法一：js104.二叉树的最大深度方法一：c方法一：js226.翻转二叉树方法一：c方法一：js101.对称二叉树方法一：c方法一：js543.二叉树的直径方法一：c方法一：js102.二叉树的层序遍历方法一：c方法一：js108.将有序数组转换为二叉搜索树方法一：c方法一：js98.验证二叉搜索树方法一：c方法一：js230.二叉搜索树中第 K 小的元素方法一：c方法一：js199.二叉树的右视图方法一：c方法一：js114.二叉树展开为链表方法一：c方法一：js105.从前序与中序遍历序列构造二叉树方法一：c方法一：js437. 路径总和 III方法一：c方法一：js236. 二叉树的最近公共祖先方法一：c方法一:js124. 二叉树中的最大路径和方法一：c方法一：js94. 二叉树的中序遍历给定一个二叉树的根节点root，返回它的中序遍历。输入：root = [1,null,2,3] 输出：[1,3,2]方法一：c中序遍历就是先访问左子树，再访问根节点，最后访问右子树。class Solution{public:vectorintans;vectorintinorderTraversal(TreeNode*root){dfs(root);returnans;}voiddfs(TreeNode*root){if(root==nullptr)return;dfs(root-left);ans.push_back(root-val);dfs(root-right);}};方法一：js// 定义二叉树节点类classTreeNode{constructor(val=0,left=null,right=null){this.val=val;this.left=left;this.right=right;}}varinorderTraversal=function(root){constans=[];// 存储遍历结果constdfs=(node)={if(node===null)return;dfs(node.left);// 左ans.push(node.val);// 中（访问节点）dfs(node.right);// 右};dfs(root);returnans;};// 测试示例：二叉树：1 - 右子树2 - 左子树3constroot=newTreeNode(1,null,newTreeNode(2,newTreeNode(3)));console.log(inorderTraversal(root));// 输出：[1,3,2]（符合中序遍历结果）104.二叉树的最大深度给定一个二叉树root，返回其最大深度。二叉树的最大深度是指从根节点到最远叶子节点的最长路径上的节点数。方法一：c深度就是树的高度，即只要左右子树其中有一个不为空，就继续往下递归，知道节点为空，向上返回。intmaxDepth(TreeNode*root){if(root==nullptr)return0;returnmax(maxDepth(root-left),maxDepth(root-right))+1;}方法一：jsvarmaxDepth=function(root){if(root===null){// 边界条件：节点为空，深度为0（对应C++的root == nullptr）return0;}// 递归计算左/右子树的最大深度，取较大值 + 1（当前节点的深度）returnMath.max(maxDepth(root.left),maxDepth(root.right))+1;};226.翻转二叉树给你一棵二叉树的根节点root，翻转这棵二叉树，并返回其根节点。输入：root = [4,2,7,1,3,6,9] 输出：[4,7,2,9,6,3,1]方法一：c对二叉树来一遍后序遍历，即先将左右子树翻转，保存反转后的左右子树的根节点，让root左右子树指针分别指向右子树，左子树。TreeNode*invertTree(TreeNode*root){if(root==nullptr)returnroot;TreeNode*left=invertTree(root-left);TreeNode*right=invertTree(root-right);root-right=left;root-left=right;returnroot;}其实翻转二叉树既可以用后序，也可以用前序，甚至中序（需要特殊处理），但后序的写法：逻辑最清晰：先搞定所有子树，再处理当前节点，不会出现指针混乱；代码更易读：左→右→中，完全贴合「先翻转子树，再交换指针」的语义；无额外风险：不会因为提前交换指针导致子树地址丢失（比如新手写前序时容易写错递归的参数）。方法一：js// 定义二叉树节点类（模拟 C++ 的 TreeNode 结构体）classTreeNode{constructor(val=0,left=null,right=null){this.val=val;// 节点值this.left=left;// 左子节点this.right=right;// 右子节点}}// 翻转二叉树的核心函数（对应你提供的 C++ 代码）functioninvertTree(root){// 递归终止条件：节点为空时直接返回if(root===null){returnroot;}// 递归翻转左、右子树constleft=invertTree(root.left);constright=invertTree(root.right);// 交换当前节点的左右子节点root.right=left;root.left=right;// 返回翻转后的当前节点returnroot;}constroot=newTreeNode(4);root.left=newTreeNode(2,newTreeNode(1),newTreeNode(3));root.right=newTreeNode(7,newTreeNode(6),newTreeNode(9));// 翻转二叉树constinvertedRoot=invertTree(root);console.log(invertedRoot);// 输出翻转后的树结构，可验证左右子节点已交换101.对称二叉树给你一个二叉树的根节点root， 检查它是否轴对称。输入：root = [1,2,2,3,4,4,3] 输出：true示例 2：输入：root = [1,2,2,null,3,null,3] 输出：false方法一：c求对称二叉树，我们只需要判断左右子树是否满足满足下面这些性质：左右子树根节点相同；2. 左子树的右子树 = 右子树的的左子树；3. 左子树的左子树 = 右子树的右子树。// 判断二叉树是否对称的主函数boolisSymmetric(TreeNode*root){returnisSameTree(root-left,root-right);// 核心逻辑：判断根节点的左右子树是否镜像对称}// 辅助函数：判断两棵树是否为镜像关系（非普通的相同树）boolisSameTree(TreeNode*t1,TreeNode*t2){if(t1==nullptrt2==nullptr)// 情况1：两个节点都为空，视为对称returntrue;if(t1==nullptr||t2==nullptr)// 情况2：一个为空一个不为空，必然不对称returnfalse;if(t1-val!=t2-val)// 情况3：节点值不相等，必然不对称returnfalse;// 递归判断：t1的左子树和t2的右子树对称，且t1的右子树和t2的左子树对称returnisSameTree(t1-left,t2-right)isSameTree(t1-right,t2-left);}两个条件不重复，是递进逻辑：先判定 “双空（合法对称）” 返回 true，再判定 “一空一非空（非法不对称）” 返回 false；若去掉第一个条件，会把 “双空” 的合法情况误判为不对称，核心逻辑直接出错。方法一：js// 定义二叉树节点类（和之前翻转二叉树的节点类一致）classTreeNode{constructor(val=0,left=null,right=null){this.val=val;// 节点值this.left=left;// 左子节点this.right=right;// 右子节点}}functionisSymmetric(root){// 边界处理：根节点为空时直接视为对称if(root===null)returntrue;returnisSameTree(root.left,root.right);// 核心逻辑：判断根节点的左右子树是否镜像对称}functionisSameTree(t1,t2){if(t1===nullt2===null){// 情况1：两个节点都为空，视为对称returntrue;}if(t1===null||t2===null){// 情况2：一个为空一个不为空，必然不对称returnfalse;}if(t1.val!==t2.val){// 情况3：节点值不相等，必然不对称returnfalse;}// 递归判断：t1的左子树和t2的右子树对称，且t1的右子树和t2的左子树对称returnisSameTree(t1.left,t2.right)isSameTree(t1.right,t2.left);}543.二叉树的直径给你一棵二叉树的根节点，返回该树的直径。二叉树的直径是指树中任意两个节点之间最长路径的长度。这条路径可能经过也可能不经过根节点root。两节点之间路径的长度由它们之间边数表示。输入：root = [1,2,3,4,5] 输出：3 解释：3 ，取路径 [4,2,1,3] 或 [5,2,1,3] 的长度。示例 2：输入：root = [1,2] 输出：1以某个节点为根节点，统计做左子树的最长路径，在统计右子树的最长路径，左右子树最长路径相加就是该二叉树的直径。递归函数向上返回该二叉树的最长路径。递归返回最长单路径：是给父节点 “递数据”，父节点只能用 “单条路的长度” 来算自己的直径；每个节点自己算直径：是用子节点递上来的 “单路径长度” 相加，得到自己这的 “最大跨度”；核心区别：直径是 “左右相加的总长度（给全局用）”，单路径是 “选最长的一条（给父节点用）”。递归计算顺序是自底向上：先算叶子节点，再算父节点，最后算根节点；每个节点返回的是最长单路径（给父节点用的 “单程距离”），计算的是直径（自己的 “总跨度”）；对于[1,2,3,4,5]这个树，最终直径是 3，核心贡献来自节点 2 的左右单路径相加（1+1=2），再结合根节点 1 的右侧路径（1），形成最长路径。方法一：cintans=0;intdiameterOfBinaryTree(TreeNode*root){depth(root);returnans;}intdepth(TreeNode*root){if(root==nullptr)return0;intleft=depth(root-left);intright=depth(root-right);ans=max(ans,left+right);returnmax(left,right)+1;}方法一：jsclassTreeNode{constructor(val=0,left=null,right=null){this.val=val;this.left=left;this.right=right;}}letmaxDiameter=0;// 全局变量记录整棵树的最大直径// 递归函数：返回以root为根的子树的【最长单路径】functiondfs(root){if(root===null)return0;// 空节点，向下走的长度为0// 1. 递归计算左右子树的【最长单路径】constleftLen=dfs(root.left);constrightLen=dfs(root.right);// 2. 计算以当前节点为根的【直径】，并更新全局最大值constcurrentDiameter=leftLen+rightLen;maxDiameter=Math.max(maxDiameter,currentDiameter);// 3. 向上返回【最长单路径】（选左/右更长的 + 自身1步）returnMath.max(leftLen,rightLen)+1;}// 主函数：计算二叉树的直径functiondiameterOfBinaryTree
leetcode-hot100-8二叉树
发布时间：2026/5/22 11:53:51
1.二叉树文章目录1.二叉树94. 二叉树的中序遍历方法一：c方法一：js104.二叉树的最大深度方法一：c方法一：js226.翻转二叉树方法一：c方法一：js101.对称二叉树方法一：c方法一：js543.二叉树的直径方法一：c方法一：js102.二叉树的层序遍历方法一：c方法一：js108.将有序数组转换为二叉搜索树方法一：c方法一：js98.验证二叉搜索树方法一：c方法一：js230.二叉搜索树中第 K 小的元素方法一：c方法一：js199.二叉树的右视图方法一：c方法一：js114.二叉树展开为链表方法一：c方法一：js105.从前序与中序遍历序列构造二叉树方法一：c方法一：js437. 路径总和 III方法一：c方法一：js236. 二叉树的最近公共祖先方法一：c方法一:js124. 二叉树中的最大路径和方法一：c方法一：js94. 二叉树的中序遍历给定一个二叉树的根节点root，返回它的中序遍历。输入：root = [1,null,2,3] 输出：[1,3,2]方法一：c中序遍历就是先访问左子树，再访问根节点，最后访问右子树。class Solution{public:vectorintans;vectorintinorderTraversal(TreeNode*root){dfs(root);returnans;}voiddfs(TreeNode*root){if(root==nullptr)return;dfs(root-left);ans.push_back(root-val);dfs(root-right);}};方法一：js// 定义二叉树节点类classTreeNode{constructor(val=0,left=null,right=null){this.val=val;this.left=left;this.right=right;}}varinorderTraversal=function(root){constans=[];// 存储遍历结果constdfs=(node)={if(node===null)return;dfs(node.left);// 左ans.push(node.val);// 中（访问节点）dfs(node.right);// 右};dfs(root);returnans;};// 测试示例：二叉树：1 - 右子树2 - 左子树3constroot=newTreeNode(1,null,newTreeNode(2,newTreeNode(3)));console.log(inorderTraversal(root));// 输出：[1,3,2]（符合中序遍历结果）104.二叉树的最大深度给定一个二叉树root，返回其最大深度。二叉树的最大深度是指从根节点到最远叶子节点的最长路径上的节点数。方法一：c深度就是树的高度，即只要左右子树其中有一个不为空，就继续往下递归，知道节点为空，向上返回。intmaxDepth(TreeNode*root){if(root==nullptr)return0;returnmax(maxDepth(root-left),maxDepth(root-right))+1;}方法一：jsvarmaxDepth=function(root){if(root===null){// 边界条件：节点为空，深度为0（对应C++的root == nullptr）return0;}// 递归计算左/右子树的最大深度，取较大值 + 1（当前节点的深度）returnMath.max(maxDepth(root.left),maxDepth(root.right))+1;};226.翻转二叉树给你一棵二叉树的根节点root，翻转这棵二叉树，并返回其根节点。输入：root = [4,2,7,1,3,6,9] 输出：[4,7,2,9,6,3,1]方法一：c对二叉树来一遍后序遍历，即先将左右子树翻转，保存反转后的左右子树的根节点，让root左右子树指针分别指向右子树，左子树。TreeNode*invertTree(TreeNode*root){if(root==nullptr)returnroot;TreeNode*left=invertTree(root-left);TreeNode*right=invertTree(root-right);root-right=left;root-left=right;returnroot;}其实翻转二叉树既可以用后序，也可以用前序，甚至中序（需要特殊处理），但后序的写法：逻辑最清晰：先搞定所有子树，再处理当前节点，不会出现指针混乱；代码更易读：左→右→中，完全贴合「先翻转子树，再交换指针」的语义；无额外风险：不会因为提前交换指针导致子树地址丢失（比如新手写前序时容易写错递归的参数）。方法一：js// 定义二叉树节点类（模拟 C++ 的 TreeNode 结构体）classTreeNode{constructor(val=0,left=null,right=null){this.val=val;// 节点值this.left=left;// 左子节点this.right=right;// 右子节点}}// 翻转二叉树的核心函数（对应你提供的 C++ 代码）functioninvertTree(root){// 递归终止条件：节点为空时直接返回if(root===null){returnroot;}// 递归翻转左、右子树constleft=invertTree(root.left);constright=invertTree(root.right);// 交换当前节点的左右子节点root.right=left;root.left=right;// 返回翻转后的当前节点returnroot;}constroot=newTreeNode(4);root.left=newTreeNode(2,newTreeNode(1),newTreeNode(3));root.right=newTreeNode(7,newTreeNode(6),newTreeNode(9));// 翻转二叉树constinvertedRoot=invertTree(root);console.log(invertedRoot);// 输出翻转后的树结构，可验证左右子节点已交换101.对称二叉树给你一个二叉树的根节点root， 检查它是否轴对称。输入：root = [1,2,2,3,4,4,3] 输出：true示例 2：输入：root = [1,2,2,null,3,null,3] 输出：false方法一：c求对称二叉树，我们只需要判断左右子树是否满足满足下面这些性质：左右子树根节点相同；2. 左子树的右子树 = 右子树的的左子树；3. 左子树的左子树 = 右子树的右子树。// 判断二叉树是否对称的主函数boolisSymmetric(TreeNode*root){returnisSameTree(root-left,root-right);// 核心逻辑：判断根节点的左右子树是否镜像对称}// 辅助函数：判断两棵树是否为镜像关系（非普通的相同树）boolisSameTree(TreeNode*t1,TreeNode*t2){if(t1==nullptrt2==nullptr)// 情况1：两个节点都为空，视为对称returntrue;if(t1==nullptr||t2==nullptr)// 情况2：一个为空一个不为空，必然不对称returnfalse;if(t1-val!=t2-val)// 情况3：节点值不相等，必然不对称returnfalse;// 递归判断：t1的左子树和t2的右子树对称，且t1的右子树和t2的左子树对称returnisSameTree(t1-left,t2-right)isSameTree(t1-right,t2-left);}两个条件不重复，是递进逻辑：先判定 “双空（合法对称）” 返回 true，再判定 “一空一非空（非法不对称）” 返回 false；若去掉第一个条件，会把 “双空” 的合法情况误判为不对称，核心逻辑直接出错。方法一：js// 定义二叉树节点类（和之前翻转二叉树的节点类一致）classTreeNode{constructor(val=0,left=null,right=null){this.val=val;// 节点值this.left=left;// 左子节点this.right=right;// 右子节点}}functionisSymmetric(root){// 边界处理：根节点为空时直接视为对称if(root===null)returntrue;returnisSameTree(root.left,root.right);// 核心逻辑：判断根节点的左右子树是否镜像对称}functionisSameTree(t1,t2){if(t1===nullt2===null){// 情况1：两个节点都为空，视为对称returntrue;}if(t1===null||t2===null){// 情况2：一个为空一个不为空，必然不对称returnfalse;}if(t1.val!==t2.val){// 情况3：节点值不相等，必然不对称returnfalse;}// 递归判断：t1的左子树和t2的右子树对称，且t1的右子树和t2的左子树对称returnisSameTree(t1.left,t2.right)isSameTree(t1.right,t2.left);}543.二叉树的直径给你一棵二叉树的根节点，返回该树的直径。二叉树的直径是指树中任意两个节点之间最长路径的长度。这条路径可能经过也可能不经过根节点root。两节点之间路径的长度由它们之间边数表示。输入：root = [1,2,3,4,5] 输出：3 解释：3 ，取路径 [4,2,1,3] 或 [5,2,1,3] 的长度。示例 2：输入：root = [1,2] 输出：1以某个节点为根节点，统计做左子树的最长路径，在统计右子树的最长路径，左右子树最长路径相加就是该二叉树的直径。递归函数向上返回该二叉树的最长路径。递归返回最长单路径：是给父节点 “递数据”，父节点只能用 “单条路的长度” 来算自己的直径；每个节点自己算直径：是用子节点递上来的 “单路径长度” 相加，得到自己这的 “最大跨度”；核心区别：直径是 “左右相加的总长度（给全局用）”，单路径是 “选最长的一条（给父节点用）”。递归计算顺序是自底向上：先算叶子节点，再算父节点，最后算根节点；每个节点返回的是最长单路径（给父节点用的 “单程距离”），计算的是直径（自己的 “总跨度”）；对于[1,2,3,4,5]这个树，最终直径是 3，核心贡献来自节点 2 的左右单路径相加（1+1=2），再结合根节点 1 的右侧路径（1），形成最长路径。方法一：cintans=0;intdiameterOfBinaryTree(TreeNode*root){depth(root);returnans;}intdepth(TreeNode*root){if(root==nullptr)return0;intleft=depth(root-left);intright=depth(root-right);ans=max(ans,left+right);returnmax(left,right)+1;}方法一：jsclassTreeNode{constructor(val=0,left=null,right=null){this.val=val;this.left=left;this.right=right;}}letmaxDiameter=0;// 全局变量记录整棵树的最大直径// 递归函数：返回以root为根的子树的【最长单路径】functiondfs(root){if(root===null)return0;// 空节点，向下走的长度为0// 1. 递归计算左右子树的【最长单路径】constleftLen=dfs(root.left);constrightLen=dfs(root.right);// 2. 计算以当前节点为根的【直径】，并更新全局最大值constcurrentDiameter=leftLen+rightLen;maxDiameter=Math.max(maxDiameter,currentDiameter);// 3. 向上返回【最长单路径】（选左/右更长的 + 自身1步）returnMath.max(leftLen,rightLen)+1;}// 主函数：计算二叉树的直径functiondiameterOfBinaryTree
