LeetCode热题100JS（44/100）第八天|二叉树的直径|二叉树的层序遍历|将有序数组转换为二叉搜索树|验证二叉树搜索树|二叉搜索树中第K小的元素

 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]
};

总结

 还可以优化~多设置一个变量，大家想想吧~