阅读 147

树形结构-对应算法详解三

文章简要概述

  • 本文主要进行树相关的算法题刷题题解记录,记录树相关算法以及如何解。

  • 这文一共有4道题,主要介绍leetcode中剑指 Offer 32 - II. 从上到下打印二叉树 II107. 二叉树的层序遍历 II103. 二叉树的锯齿形层序遍历、和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` ,返回其节点值 **自底向上的层序遍历** 。 (即按从叶子节点所在层到根节点所在的层,逐层从左向右遍历) 复制代码

示例:

tree.jpeg

输入: 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` ,返回其节点值的 **锯齿形层序遍历** 。(即先从左往右,再从右往左进行下一层遍历,以此类推,层与层之间交替进行)。 复制代码

示例:

tree1.jpeg

输入: 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 。 复制代码

示例:

tree1.jpeg

输入: 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

文章分类
代码人生
版权声明:本站是系统测试站点,无实际运营。本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容, 请发送邮件至 XXXXXXo@163.com 举报,一经查实,本站将立刻删除。
相关推荐