Open ChenJiaH opened 4 years ago
首发于微信公众号《前端成长记》,写于 2019.12.06
本文记录刷题过程中的整个思考过程,以供参考。主要内容涵盖:
题目地址
给定两个二叉树,编写一个函数来检验它们是否相同。
如果两个树在结构上相同,并且节点具有相同的值,则认为它们是相同的。
示例:
输入: 1 1 / \ / \ 2 3 2 3 [1,2,3], [1,2,3] 输出: true 输入: 1 1 / \ 2 2 [1,2], [1,null,2] 输出: false 输入: 1 1 / \ / \ 2 1 1 2 [1,2,1], [1,1,2] 输出: false
题目直接说了是二叉树,而二叉树的遍历方式有两种:深度优先和广度优先,我就从这两个思路来作答。
Ⅰ.深度优先
代码:
/** * @param {TreeNode} p * @param {TreeNode} q * @return {boolean} */ var isSameTree = function(p, q) { if (p === null && q === null) return true if (p === null || q === null) return false if (p.val !== q.val) return false return isSameTree(p.left, q.left) && isSameTree(p.right, q.right) };
结果:
O(n)
n
Ⅱ.广度优先
/** * @param {TreeNode} p * @param {TreeNode} q * @return {boolean} */ var isSameTree = function(p, q) { if (p === null && q === null) return true if (p === null || q === null) return false let pQ =[p] // 左侧比较队列 let qQ =[q] // 右侧比较队列 let res = true while(true) { if (!pQ.length || !qQ.length) { res = pQ.length === qQ.length break } // 当前比较节点 let curP = pQ.shift() let curQ = qQ.shift() if ((curP && !curQ) || (!curP && curQ) || (curP && curQ && curP.val !== curQ.val)) { res = false break } else { let pL = curP ? curP.left : null let pR = curP ? curP.right : null if (pL || pR) { // 至少一个存在才有意义 pQ.push(pL, pR) // 依次推入比较数组,实际上就是广度优先 } let qL = curQ ? curQ.left : null let qR = curQ ? curQ.right : null if (qL || qR) { // 至少一个存在才有意义 qQ.push(qL, qR) // 依次推入比较数组,实际上就是广度优先 } } } return res };
思路基本上都是这两种,未发现方向不同的解法。
一般碰到二叉树的题,要么就深度遍历,要么就广度遍历。深度优先,也叫先序遍历。
给定一个二叉树,检查它是否是镜像对称的。
例如,二叉树 [1,2,2,3,4,4,3] 是对称的。
[1,2,2,3,4,4,3]
1 / \ 2 2 / \ / \ 3 4 4 3
但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:
[1,2,2,null,3,null,3]
1 / \ 2 2 \ \ 3 3
说明:
如果你可以运用递归和迭代两种方法解决这个问题,会很加分。
还是一道二叉树的题,所以常规思路就是遍历操作,深度优先或广度优先都可。镜像对称可以观察到很明显的特点是有相同的根节点值,且每个树的右子树与另一个树的左字数对称相等。深度优先的方式,其实就是递归的思路,符合题目的说明。
/** * @param {TreeNode} root * @return {boolean} */ var isSymmetric = function(root) { function isMirror (l, r) { if (l === null && r === null) return true if (l === null || r === null) return false return l.val === r.val && isMirror(l.left, r.right) && isMirror(l.right, r.left) } return isMirror(root, root) };
/** * @param {TreeNode} root * @return {boolean} */ var isSymmetric = function(root) { if (root === null) return true // 初始队列 let q = [root.left, root.right] // 依次将同级push进队列,每次取两个对称节点进行判断 while(q.length) { let l = q.shift() let r = q.shift() if (l === null && r === null) continue if (l === null || r === null) return false if (l.val !== r.val) return false q.push(l.left, r.right, l.right, r.left) } return true };
看到一个有意思的思路,将树按照左中右的顺序输入到数组,加上层数,该数组也是对称的。
Ⅰ.左中右顺序输出数组
/** * @param {TreeNode} root * @return {boolean} */ var isSymmetric = function(root) { if (root === null) return true // 输出数组 let arr = [] search(arr, root, 1); // 入参分别为输出,节点和层级 function search(output, n, k) { if (n.left !== null) { search(output, n.left, k+1) } if (n.right !== null) { search(output, n.right, k + 1); } } //判断是否对称 let i = 0, j = arr.length - 1 while (i < j) { if (arr[i] != arr[j]) { return false } i++ j-- } return true };
这道题的大致解法都是遍历节点或者利用队列,只是在递归的细节上会有些差异。左中右输出数组的思路很清奇,虽然效率明显会更低下,但是不失为一种思路。
给定一个二叉树,找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
给定二叉树 [3,9,20,null,null,15,7],
[3,9,20,null,null,15,7]
3 / \ 9 20 / \ 15 7
返回它的最大深度 3 。
这道题最基本的思路就是计算出每条子节点的深度,再进行比较。为了提升效率,可以增加同级比对,去除不可能是最长节点的叶节点计算。
所以这里我就用以下几种思路来实现深度优先算法。
Ⅰ.递归
/** * @param {TreeNode} root * @return {number} */ var maxDepth = function(root) { if (root === null) return 0 // 左侧子树的最大高度 let l = maxDepth(root.left) // 右侧子树的最大高度 let r = maxDepth(root.right) return Math.max(l, r) + 1 };
Ⅱ.利用队列
/** * @param {TreeNode} root * @return {number} */ var maxDepth = function(root) { if (root === null) return 0 // 队列 let q = [root] let dep = 0 while(q.length) { let size = q.length dep++ while(size > 0) { let node = q.shift() if (node.left !== null) q.push(node.left) if (node.right !== null) q.push(node.right) size-- } } return dep };
这里看到一个用栈的角度来实现的,取栈高度的最大值,其他的基本都是循环的细节差异,大体思路一致。
Ⅰ.利用栈
/** * @param {TreeNode} root * @return {number} */ var maxDepth = function(root) { if (root === null) return 0 // 栈 let s = [{ node: root, dep: 1 }] let dep = 0 while(s.length) { // 先进后出 var cur = s.pop() if (cur.node !== null) { let curDep = cur.dep dep = Math.max(dep, curDep) if (cur.node.left !== null) s.push({node: cur.node.left, dep: curDep + 1}) if (cur.node.right !== null) s.push({node: cur.node.right, dep: curDep + 1}) } } return dep };
二叉树的操作,一般就是深度优先和广度优先,所以基本上就朝这两个方向上去解,然后进行优化就可以了。
给定一个二叉树,返回其节点值自底向上的层次遍历。 (即按从叶子节点所在层到根节点所在的层,逐层从左向右遍历)
例如:
给定二叉树 [3,9,20,null,null,15,7],
返回其自底向上的层次遍历为:
[ [15,7], [9,20], [3] ]
这道题在我看来还是两种方式,深度优先和广度优先。
/** * @param {TreeNode} root * @return {number[][]} */ var levelOrderBottom = function(root) { // 当前层级标识 let idx = 0 let res = [] function levelOrder(node, floor, arr) { if (node === null) return arr if(arr[floor]) { arr[floor].push(node.val) } else { arr[floor] = [node.val] } levelOrder(node.left, floor + 1, arr) levelOrder(node.right, floor + 1, arr) return arr } return levelOrder(root, idx, res).reverse() };
/** * @param {TreeNode} root * @return {number[][]} */ var levelOrderBottom = function(root) { if (root === null) return [] // 初始队列 let q = [root] let res = [] while(q.length) { // 当前层节点数量 const count = q.length let curArr = [] for(let i = 0; i < count;i++) { const node = q.shift() curArr.push(node.val) // 将子节点依次推入队列 if (node.left) q.push(node.left) if (node.right ) q.push(node.right ) } res.push(curArr) } return res.reverse() };
没有看到什么特别的解法,主要都是按 BFS 和 DFS 来处理,要么迭代,要么递归等等。
这里就介绍下别的吧,在第一种解法中我们使用的是前序优先,当然用中序优先或后序优先也可以,下面代码可以说明区别:
// 先序,顺序为 根 -> 左 -> 右 function levelOrder(node, floor, arr) { if(arr[floor]) { arr[floor].push(node.val) } else { arr[floor] = [node.val] } levelOrder(node.left, floor + 1, arr) levelOrder(node.right, floor + 1, arr) return arr } // 中序,顺序为 左 -> 根 -> 右 function levelOrder(node, floor, arr) { levelOrder(node.left, floor + 1, arr) if(arr[floor]) { arr[floor].push(node.val) } else { arr[floor] = [node.val] } levelOrder(node.right, floor + 1, arr) return arr } // 后序,顺序为 左 -> 右 -> 根 function levelOrder(node, floor, arr) { levelOrder(node.left, floor + 1, arr) levelOrder(node.right, floor + 1, arr) if(arr[floor]) { arr[floor].push(node.val) } else { arr[floor] = [node.val] } return arr }
二叉树的题目就根据情况在深度优先和广度优先中择优选择即可,基本不会有太大的问题。
将一个按照升序排列的有序数组,转换为一棵高度平衡二叉搜索树。
本题中,一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
示例:
给定有序数组: [-10,-3,0,5,9], 一个可能的答案是:[0,-3,9,-10,null,5],它可以表示下面这个高度平衡二叉搜索树: 0 / \ -3 9 / / -10 5
这里有两点要注意的:高度平衡二叉树要求每个节点的左右两个子树的高度差的绝对值不超过 1;而二叉搜索树要求左子树上所有节点值小于根节点,右子树上所有节点值大于根节点。
而题目给出的是一个有序的数组,所以可以直接考虑二分后进行处理,我这就直接递归作答:找到根节点,递归生成左右子树。
/** * @param {number[]} nums * @return {TreeNode} */ var sortedArrayToBST = function(nums) { if (!nums.length) return null // 中位数,用偏移避免溢出 const mid = nums.length >>> 1 const root = new TreeNode(nums[mid]) root.left = sortedArrayToBST(nums.slice(0, mid)) root.right = sortedArrayToBST(nums.slice(mid + 1)) return root };
这里看到另外一种解法,先创建一个平衡二叉树,然后中序遍历树同时遍历数组即可,因为中序遍历出来的刚好是有序数组。
Ⅰ.创建树后中序遍历数组赋值
/** * @param {number[]} nums * @return {TreeNode} */ var sortedArrayToBST = function(nums) { if (!nums.length) return null // 节点总数 let len = nums.length let root = new TreeNode(-1); let q = [root] // 已经创建了根节点 len-- while(len) { const node = q.shift() // 左子树 const l = new TreeNode(-1) q.push(l) node.left = l len-- if (len) { // 右子树 const r = new TreeNode(-1) q.push(r) node.right = r len-- } } let i = 0 inorder(root) function inorder(node) { if (node === null) return inorder(node.left) node.val = nums[i++] inorder(node.right) } return root };
这里其实是个逆向思维,之前是二叉树输出数组,现在变成数组转成二叉树。刚好可以翻一下前序中序和后序的区别,这里中序就可以了。不过这道题我还是更推荐递归二分求解。
(完)
本文为原创文章,可能会更新知识点及修正错误,因此转载请保留原出处,方便溯源,避免陈旧错误知识的误导,同时有更好的阅读体验 如果能给您带去些许帮助,欢迎 ⭐️star 或 ✏️ fork (转载请注明出处:https://chenjiahao.xyz)
背景
本文记录刷题过程中的整个思考过程,以供参考。主要内容涵盖:
目录
Easy
100.相同的树
题目地址
题目描述
给定两个二叉树,编写一个函数来检验它们是否相同。
如果两个树在结构上相同,并且节点具有相同的值,则认为它们是相同的。
示例:
题目分析设想
题目直接说了是二叉树,而二叉树的遍历方式有两种:深度优先和广度优先,我就从这两个思路来作答。
编写代码验证
Ⅰ.深度优先
代码:
结果:
O(n)
,n
为节点个数Ⅱ.广度优先
代码:
结果:
O(n)
,n
为节点个数查阅他人解法
思路基本上都是这两种,未发现方向不同的解法。
思考总结
一般碰到二叉树的题,要么就深度遍历,要么就广度遍历。深度优先,也叫先序遍历。
101.对称二叉树
题目地址
题目描述
给定一个二叉树,检查它是否是镜像对称的。
例如,二叉树
[1,2,2,3,4,4,3]
是对称的。示例:
但是下面这个
[1,2,2,null,3,null,3]
则不是镜像对称的:说明:
如果你可以运用递归和迭代两种方法解决这个问题,会很加分。
题目分析设想
还是一道二叉树的题,所以常规思路就是遍历操作,深度优先或广度优先都可。镜像对称可以观察到很明显的特点是有相同的根节点值,且每个树的右子树与另一个树的左字数对称相等。深度优先的方式,其实就是递归的思路,符合题目的说明。
编写代码验证
Ⅰ.深度优先
代码:
结果:
O(n)
,n
为节点个数Ⅱ.广度优先
代码:
结果:
O(n)
,n
为节点个数查阅他人解法
看到一个有意思的思路,将树按照左中右的顺序输入到数组,加上层数,该数组也是对称的。
Ⅰ.左中右顺序输出数组
代码:
结果:
O(n)
,n
为节点个数思考总结
这道题的大致解法都是遍历节点或者利用队列,只是在递归的细节上会有些差异。左中右输出数组的思路很清奇,虽然效率明显会更低下,但是不失为一种思路。
104.二叉树的最大深度
题目地址
题目描述
给定一个二叉树,找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
示例:
给定二叉树
[3,9,20,null,null,15,7]
,返回它的最大深度 3 。
题目分析设想
这道题最基本的思路就是计算出每条子节点的深度,再进行比较。为了提升效率,可以增加同级比对,去除不可能是最长节点的叶节点计算。
所以这里我就用以下几种思路来实现深度优先算法。
编写代码验证
Ⅰ.递归
代码:
结果:
O(n)
,n
为节点个数Ⅱ.利用队列
代码:
结果:
O(n)
,n
为节点个数查阅他人解法
这里看到一个用栈的角度来实现的,取栈高度的最大值,其他的基本都是循环的细节差异,大体思路一致。
Ⅰ.利用栈
代码:
结果:
O(n)
,n
为节点个数思考总结
二叉树的操作,一般就是深度优先和广度优先,所以基本上就朝这两个方向上去解,然后进行优化就可以了。
107.二叉树的层次遍历II
题目地址
题目描述
给定一个二叉树,返回其节点值自底向上的层次遍历。 (即按从叶子节点所在层到根节点所在的层,逐层从左向右遍历)
例如:
给定二叉树
[3,9,20,null,null,15,7]
,返回其自底向上的层次遍历为:
题目分析设想
这道题在我看来还是两种方式,深度优先和广度优先。
编写代码验证
Ⅰ.深度优先
代码:
结果:
O(n)
,n
为节点个数Ⅱ.广度优先
代码:
结果:
O(n)
,n
为节点个数查阅他人解法
没有看到什么特别的解法,主要都是按 BFS 和 DFS 来处理,要么迭代,要么递归等等。
这里就介绍下别的吧,在第一种解法中我们使用的是前序优先,当然用中序优先或后序优先也可以,下面代码可以说明区别:
思考总结
二叉树的题目就根据情况在深度优先和广度优先中择优选择即可,基本不会有太大的问题。
108.将有序数组转换为二叉搜索树
题目地址
题目描述
将一个按照升序排列的有序数组,转换为一棵高度平衡二叉搜索树。
本题中,一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
示例:
题目分析设想
这里有两点要注意的:高度平衡二叉树要求每个节点的左右两个子树的高度差的绝对值不超过 1;而二叉搜索树要求左子树上所有节点值小于根节点,右子树上所有节点值大于根节点。
而题目给出的是一个有序的数组,所以可以直接考虑二分后进行处理,我这就直接递归作答:找到根节点,递归生成左右子树。
编写代码验证
Ⅰ.递归
代码:
结果:
O(n)
查阅他人解法
这里看到另外一种解法,先创建一个平衡二叉树,然后中序遍历树同时遍历数组即可,因为中序遍历出来的刚好是有序数组。
Ⅰ.创建树后中序遍历数组赋值
代码:
结果:
O(n)
思考总结
这里其实是个逆向思维,之前是二叉树输出数组,现在变成数组转成二叉树。刚好可以翻一下前序中序和后序的区别,这里中序就可以了。不过这道题我还是更推荐递归二分求解。
(完)