543. 二叉树的直径
题目链接：543. 二叉树的直径
难度：简单
刷题状态：1刷
新知识：
解题过程
思考
示例 1：
输入：root = [1,2,3,4,5] 输出：3 解释：3 ，取路径 [4,2,1,3] 或 [5,2,1,3] 的长度。
没什么思路，直接看答案
题解分析
参考题解链接：【视频】彻底掌握直径 DP！从二叉树到一般树！（Python/Java/C++/C/Go/JS/Rust）
详细分析如下
/*** 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 diameterOfBinaryTree = function(root) {let res=0function dfs(node){//统计的是路径长度，不是节点个数if(!node) return -1let llen=dfs(node.left)+1//左子树最大链长+1let rlen=dfs(node.right)+1//右子树最大链长+1res=Math.max(res,llen+rlen)//两条链拼成路径return Math.max(llen,rlen)//当前子数最大链长}dfs(root)return res
};手搓答案（无非废话版）
/*** 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 diameterOfBinaryTree = function(root) {let res=0function dfs(root){if(!root) return -1let llen=dfs(root.left)+1let rlen=dfs(root.right)+1res=Math.max(res,llen+rlen)return Math.max(llen,rlen)}dfs(root)return res
};总结
注意这里返回的是//当前子数最大链长return Math.max(llen,rlen)
102. 二叉树的层序遍历
题目链接：102. 二叉树的层序遍历
难度：中等
刷题状态：2刷
新知识：
- `[...map.values()]` // 返回按深度排序的节点值数组
解题过程
思考
示例 1：
输入：root = [1,2,3,4,5] 输出：3 解释：3 ，取路径 [4,2,1,3] 或 [5,2,1,3] 的长度。
放下1刷的过程在题解，虽然写过但不记得咋写的了，直接看答案吧
题解分析
参考题解链接：二叉树的层序遍历
详细分析如下
/*** 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) {let map=new Map()function dfs(node,depth){if(!node) return depthlet leftDepth=dfs(node.left,depth+1)let rightDepth=dfs(node.right,depth+1)// console.log(node.val,leftDepth)if(!map.has(leftDepth)){map.set(leftDepth,[])}map.get(leftDepth).push(node.val)return depth}dfs(root,-1)let res=Array.from(map.entries()).sort((a,b)=>a[0]-b[0]).map(([i,val])=>val)return res
};手搓答案（无非废话版）
/*** 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) {let map=new Map()function dfs(node,depth){if(!node) return depthif(!map.has(depth)) map.set(depth,[])map.get(depth).push(node.val)dfs(node.left,depth+1)dfs(node.right,depth+1)return depth}dfs(root,0)return [...map.values()]
};总结
题解是逆向填入的的，我觉得手撕的正向填入好理解一点
108. 将有序数组转换为二叉搜索树
题目链接：
108. 将有序数组转换为二叉搜索树
难度：简单
刷题状态：1刷
新知识：
解题过程
思考
示例 1：
输入：nums = [-10,-3,0,5,9] 输出：[0,-3,9,-10,null,5] 解释：[0,-10,5,null,-3,null,9] 也将被视为正确答案：
平衡二叉树 是指该树所有节点的左右子树的高度相差不超过 1。
不会，直接看答案
题解分析
参考题解链接：二叉树的层序遍历
详细分析如下
/*** 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 {number[]} nums* @return {TreeNode}*/
var sortedArrayToBST = function(nums) {function dfs(lower,higher){if(lower>higher) return null//找中间的let mid=lower+Math.floor((higher-lower)/2)let root=new TreeNode(nums[mid])//连接左子树root.left=dfs(lower,mid-1)//连接右子树root.right=dfs(mid+1,higher)return root}return dfs(0,nums.length-1)
};手搓答案（无非废话版）
/*** 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 {number[]} nums* @return {TreeNode}*/
var sortedArrayToBST = function(nums) {function dfs(lower,higher){if(lower>higher) return nulllet mid=lower+Math.floor((higher-lower)/2)let root=new TreeNode(nums[mid])root.left=dfs(lower,mid-1)root.right=dfs(mid+1,higher)return root}return dfs(0,nums.length-1)
};总结
递归解法，感觉二叉树的都是套路，就是得多练，找到套路
98. 验证二叉搜索树
题目链接：98. 验证二叉搜索树
难度：中等
刷题状态：2刷
新知识：
解题过程
思考
示例 1：
输入：root = [2,1,3] 输出：true
注意是左子树，右子树，不行，实在是忘了，直接看答案吧，这么基础的题！！！！
放下1刷过程在题解
题解分析
参考题解链接：【视频】前序中序后序，三种方法，一个视频讲透！（Python/Java/C++/Go/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 isValidBST = function(root,left=-Infinity,right=Infinity) {
// if(!root){
// return true
// }
// let l=isValidBST(root.left,left,root.val)
// let r=isValidBST(root.right,root.val,right)
// return left<root.val&&root.val<right&&l&&r
// };// var isValidBST = function(root) {
// let pre=-Infinity
// function dfs(node){
// if(!node){
// return true
// }
// console.log('node',node.val)
// if(!dfs(node.left)||node.val<=pre){
// return false
// }
// pre=node.val
// return dfs(node.right)
// }
// return dfs(root)
// };var isValidBST =function(root){function dfs(node){if(!node) return [Infinity,-Infinity]console.log(node.val)let [lMin,lMax]=dfs(node.left)let [rMin,rMax]=dfs(node.right)let x=node.valif(x<lMax||x>rMin) return [-Infinity,Infinity]return [Math.min(lMin,x),Math.max(rMax,x)]}let a=dfs(root)[1]return a!=Infinity
}手搓答案（无非废话版）
/*** 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 isValidBST =function(root){// //前序遍历// function dfs(node,left=-Infinity,right=Infinity){// if(!node) return true// let l=dfs(node.left,left,node.val)// let r=dfs(node.right,node.val,right)// return left<node.val&&node.val<right&&l&&r// }// return dfs(root)//中序遍历//（中序遍历应该是严格递增的）//这个变量用于记录中序遍历过程中上一个访问的节点的值，以便检查当前节点值是否大于上一个节点值，// let pre=-Infinity// function dfs(node){// if(!node) return true// if(!dfs(node.left)||node.val<=pre) return false// pre=node.val// return dfs(node.right)// }// return dfs(root)//后序遍历function dfs(node){//确保下一次的比较if(!node) return [Infinity,-Infinity]let [lMin,lMax]=dfs(node.left)let [rMin,rMax]=dfs(node.right)let x=node.val//说明已经不是二叉树了if(x<=lMax||x>=rMin) return [-Infinity, Infinity]return [Math.min(lMin,x),Math.max(x,rMax)]}return dfs(root)[1]==Infinity?false:true
}总结
经典题目！！！三种方法都要记得！我觉得中序的最好理解
230. 二叉搜索树中第 K 小的元素
题目链接：230. 二叉搜索树中第 K 小的元素
难度：中等
刷题状态：2刷
新知识：
解题过程
思考
示例 1：
输入：root = [3,1,4,null,2], k = 1 输出：1
放下1刷过程在题解
题解分析
参考题解链接：二叉搜索树中第K小的元素
详细分析如下
/*** 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} k* @return {number}*/
var kthSmallest = function(root, k) {let a=[]function dfs(node){if(!node) return dfs(node.left)if(a.length<k){a.push(node.val)}dfs(node.right)}dfs(root)return a[a.length-1]
};手搓答案（无非废话版）
/*** 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} k* @return {number}*/
var kthSmallest = function(root, k) {let nums=[]function dfs(node){if(!node) return dfs(node.left)if(nums.length<k) nums.push(node.val)dfs(node.right)}dfs(root)return nums[k-1]
};总结
还可以优化~多设置一个变量，大家想想吧~
