树形结构-对应算法详解三
文章简要概述
本文主要进行树相关的算法题刷题题解记录,记录树相关算法以及如何解。
这文一共有4道题,主要介绍leetcode中
剑指 Offer 32 - II. 从上到下打印二叉树 II
、107. 二叉树的层序遍历 II
、103. 二叉树的锯齿形层序遍历
、和110. 平衡二叉树
的解题思路。
与树相关算法
剑指 Offer 32 - II. 从上到下打印二叉树 II
剑指 Offer 32 - II. 从上到下打印二叉树 II -- leetcode
题目大意:
从上到下按层打印二叉树,同一层的节点按从左到右的顺序打印,每一层打印到一行。 复制代码
示例
给定二叉树:
[3,9,20,null,null,15,7]
3 / \ 9 20 / \ 15 7 复制代码返回其层次遍历结果:
[ [3], [9,20], [15,7] ]
解题思路:
采用递归加上队列的方式
先将树的每一层元素放入队列中,然后从队列的头部取出元素,放入到结果数组中。
重复操作,即可得到每一层的值。
代码:
/** * @param {TreeNode} root * @return {number[][]} */ var levelOrder = function(root) { if(!root) return []; const res = []; const cur = [root]; while(cur.length != 0) { const dep = []; for(i = cur.length; i>0;i--) { const node = cur.shift(); dep.push(node.val); if (node.left != null) cur.push(node.left); if (node.right != null) cur.push(node.right); } res.push(dep); } return res; }; 复制代码
107. 二叉树的层序遍历 II
107. 二叉树的层序遍历 II -- leetcode 题目大意:
给你二叉树的根节点 `root` ,返回其节点值 **自底向上的层序遍历** 。 (即按从叶子节点所在层到根节点所在的层,逐层从左向右遍历) 复制代码
示例:
输入: root = [3,9,20,null,null,15,7]
输出: [[15,7],[9,20],[3]]
解题思路:
这道题和上一道题基本一样,只不过是把结果反转了一下。
采用递归,将每一层的数据放入到数组中,在将数组进行反转即可
数组反转也可以用首尾交换,直到中间相遇为止
代码:
function level(root, dep, res) { if (!root) return null; if (dep === res.length) res.push(new Array()); res[dep].push(root.val); level(root.left, dep + 1, res); level(root.right, dep + 1, res); } /** * @param {TreeNode} root * @return {number[][]} */ var levelOrderBottom = function(root) { const res = []; level(root, 0, res); return res.reverse() }; 复制代码
103. 二叉树的锯齿形层序遍历
103. 二叉树的锯齿形层序遍历--leetcode
题目大意:
给你二叉树的根节点 `root` ,返回其节点值的 **锯齿形层序遍历** 。(即先从左往右,再从右往左进行下一层遍历,以此类推,层与层之间交替进行)。 复制代码
示例:
输入: root = [3,9,20,null,null,15,7]
输出: [[3],[20,9],[15,7]]
解题思路:
还是接着上一题进行的变形。
一样采用递归得到每一层的数值,然后然后奇数下标的方式,反转该层的数据,即可得到锯齿形
代码:
function level(root, dep, res) { if (!root) return null; if (dep === res.length) { res.push(new Array()); } res[dep].push(root.val); level(root.left, dep + 1, res); level(root.right, dep + 1, res); } /** * @param {TreeNode} root * @return {number[][]} */ var zigzagLevelOrder = function(root) { const res = []; level(root, 0, res); return res.map((item, index) => { if(index % 2 === 1) { item.reverse() } return item; }) }; 复制代码
110. 平衡二叉树
110. 平衡二叉树--leetcode
题目大意:
给定一个二叉树,判断它是否是高度平衡的二叉树。 本题中,一棵高度平衡二叉树定义为: 一个二叉树*每个节点* 的左右两个子树的高度差的绝对值不超过 1 。 复制代码
示例:
输入: root = [3,9,20,null,null,15,7]
输出: true
解题思路:
递归获取当前树的左子树和右子树的高度
比较左右子树的高度差是不是大于1,大于1的计数为负数。
比较当前左右子树的高度值是不是小于0, 小于0的计数位负数。
当前树的高度等于左子树的高度和右子树的高度的最大值加1
最后比较树的高度是不是大于等于 0 即可
代码:
function getHeight(root) { if (!root) return 0; const l = getHeight(root.left); const r = getHeight(root.right); if (r < 0 || l < 0) return -2; if (Math.abs(l-r) > 1) return -2; return Math.max(l, r) + 1; } /** * @param {TreeNode} root * @return {boolean} */ var isBalanced = function(root) { return getHeight(root) >= 0; }; 复制代码
结束语
数据结构与算法相关的练习题会持续输出,一起来学习,持续关注。当前是树部分。后期还会有其他类型的数据结构,题目来源于leetcode。
作者:查_克拉
链接:https://juejin.cn/post/7054170629238423583