一杯绿茶

一杯绿茶 查看完整档案

杭州编辑  |  填写毕业院校海康威视  |  前端开发 编辑填写个人主网站
编辑
_ | |__ _ _ __ _ | '_ \| | | |/ _` | | |_) | |_| | (_| | |_.__/ \__,_|\__, | |___/ 该用户太懒什么也没留下

个人动态

一杯绿茶 发布了文章 · 10月18日

JS生成链表和二叉树

最近刷算法题,经常有链表和二叉树的结构,在线运行代码都是直接传入链表或者二叉树的头节点,但是JS中没有这样的结构,本地没办法进行调试。今天专门写了下JS生成链表和二叉树的方法,下次本地调试就可以直接生成测试用例了。

链表生成

代码如下:

// ListNode构造器,用于创建链表的每个节点
class ListNode {
    constructor(val, next) {
        this.val = (val == undefined ? 0 : val);
        this.next = (next == undefined ? null : next);
    }
}

// 生成链表
function generateLinklist(arr) {
    let head = new ListNode(arr[0]), // 初始化第一个节点作为头节点
        curr = head; // curr指针保存当前节点
    for(let i=1; i<arr.length; i++) {
        curr.next = new ListNode(arr[i]); // 创建next节点
        curr = curr.next; // curr后移一位
    }
    return head // 返回头节点
}

// 调用
const head = generateLinklist([1, 2, 3, 4]);
console.log(head); // 1 -> 2 -> 3 -> 4

实现思路还是比较简单的,但是有一个地方需要注意,curr只能保存当前节点,即下一节点还没创建的时候不能提前移动。生成链表的方法本人最开始是这样写的:

// 注意,下面这段代码是错误的
function generateLinklist(arr) {
    let obj = new Linklist(arr[0]),
        curr = obj.next;
    for(let i=1; i<arr.length; i++) {
        curr = new Linklist(arr[i]);
        curr = curr.next;
    }
    return obj
}

上面的代码咋一看好像也没问题,但是拿上面用例进行测试的时候发现返回的链表只有一个节点,后面都不见了:

ListNode { val: 1, next: null }

这段代码的问题就在于,curr提前进行移动了。上面的代码中,先初始化第一个节点obj作为头节点,然后curr = obj.next的本意是希望curr指向obj的下一节点。但是curr并没有指向“下一节点”,而是指向了null,因为下一节点根本还没创建。因为obj.next == null,所以curr = obj.next相当于curr = null,如下图所示:

image.png

这样一来,执行curr = new Linklist(arr[i]);的时候,链表的第二个节点的指针其实是赋给了curr,而不是obj.next

image.png

后面每一次for循环,都是先将新的节点指针赋给curr,然后执行curr = curr.next;curr的值改为null,而这些操作都与obj无关,obj还是最开始那个创建的头节点。

所以从这里得出一个结论,当下一节点还未创建的时候,指针不能提前移动。在第一段代码中,我们看到是先创建节点,再移动curr指针的。

二叉树生成

层序遍历的反向操作,也是利用队列实现,代码如下:

// treeNode构造器
class treeNode {
    constructor(val, left, right) {
        this.val = (val == undefined ? 0 : val);
        this.left = (left == undefined ? null : left);
        this.right = (right == undefined ? null : right);
    }
}

// 生成二叉树
function generateBinarySearchTree(arr) {
    let root = new treeNode(arr[0]),
        curr = root,
        queue = new Array(),
        n = 0;
    queue.push(curr);
    while(queue.length > 0) {
        let size = queue.length;
        for(let i=0; i<size; i++) {
            curr = queue.pop();
            curr.left = arr[n+1] ? new treeNode(arr[n+1]) : null;
            curr.left && queue.unshift(curr.left); // 如果是null就不入队
            n++;

            curr.right = arr[n+1] ? new treeNode(arr[n+1]) : null;
            curr.right && queue.unshift(curr.right); // 如果是null就不入队
            n++;
        }
    }
    return root
}

generateBinarySearchTree([1, 2, 3, 4, 5, 6, 7])

代码感觉有些地方可以优化,有空再改下。

查看原文

赞 0 收藏 0 评论 0

一杯绿茶 发布了文章 · 10月13日

二叉树遍历JS实现和LeetCode题解

基本概念

二叉树遍历主要为深度优先(DFS)和广度优先(BFS),其中深度优先遍历包括前序、中序、后序,广度优先遍历也叫层序遍历。
image.png
深度优先三种方法遍历顺序:
image.png

其实很好记,就是中间节点在最前面、中间和最后面输出,而左右的相对顺序是固定的。

例如下面这棵树:

    1
   / \
  2   3
 / \ / \
4  5 6  7

前序遍历:1, 2, 4, 5, 3, 6, 7
中序遍历:4, 2, 5, 1, 6, 3, 7
后序遍历:4, 5, 2, 6, 7, 3, 1

深度优先和广度优先都能通过递归实现,由于递归方法过于简单,面试考察的通常是非递归实现。深度优先的非递归方法通过堆栈实现,广度优先的非递归方法通过队列实现

递归实现

前序遍历:

function preOrder(root) {
    if (root == null)
        return;
    console.log(root.val); // 输出控制
    preOrder(root.left);
    preOrder(root.right);
}

而中序遍历和后序遍历则只需修改输出控制的位置。

中序遍历:

function inOrder(root) {
    if (root == null)
        return;
    inOrder(root.left);
    console.log(root.val); // 输出控制
    inOrder(root.right);
}

后序遍历:

function postOrder(root) {
    if (root == null)
        return;
    postOrder(root.left);
    postOrder(root.right);
    console.log(root.val); // 输出控制
}

非递归实现

非递归版本使用堆栈实现,三种遍历方法主要是压栈弹栈的顺序不同。

前序遍历

一开始先把根节点压栈,每次弹出栈顶元素的同时输出该元素,然后把栈顶元素的右节点、左节点分别入栈(如果有的话,为空则不用);直到栈为空则停止。

image.png

代码如下:

function preOrderByStack(root) {
    let res = new Array();
    if (root == null) // 边界判断
        return res;
    let stack = new Array();
    stack.push(root); // 先把根节点压栈
    while (stack.length > 0) {
        root = stack.pop(); // 弹出当前栈顶元素
        res.push(root.val); // 保存结果
        if (root.right != null) {
            stack.push(root.right); // 先压入右节点
        }
        if (root.left != null) {
            stack.push(root.left); // 再压入左节点
        }
    }
    return res;
}

上面的代码复用了root变量,好处就是不使用额外的变量,降低空间复杂度。

后序遍历

后序遍历有一种非常trick的做法。我们知道先序遍历为中左右,而后序遍历为左右中,我们把后序遍历反过来,就是中右左,是不是发现和先序遍历有点像了?我们先序遍历采用了先压入右节点再压入左节点的方式得到了中左右的顺序,那么我们只要先压入左节点,再压入右节点,就能得到中右左的顺序,这里只要保存结果的时候从前往后插入,就变成了我们想要的后序遍历了:左右中

function preOrderByStack(root) {
    let res = new Array();
    if (root == null)
        return res;
    let stack = new Array();
    stack.push(root);
    while (stack.length > 0) {
        root = stack.pop();
        res.unshift(root.val); // 从数组头部添加结果
        if (root.left != null) {
            stack.push(root.left); // 先压入左节点
        }
        if (root.right != null) {
            stack.push(root.right); // 再压入右节点
        }
    }
    return res;
}

后序遍历可以求二叉树的深度。

中序遍历

当前节点只要有左节点,就将其左节点压栈,并且当前节点向其左节点方向移动,直到当前节点为空,说明此时位于最左下方的节点的空左节点处,那么接下来我们就需要弹栈获取栈顶,输出元素,然后移动到栈顶节点的右节点处。

image.png

代码如下:

function inOrderByStack(root) {
    let res = new Array();
    let stack = new Array();
    while (stack.length > 0 || (root != null)) {
        if (root != null) { // 当前节点非空,压栈后向左移动
            stack.push(root);
            root = root.left;
        } else { // 当前节点为空,弹栈输出后向右移动
            root = stack.pop();
            res.push(root.val);
            root = root.right;
        }
    }
    return res;
}

上面介绍的三种方法可以用于遍历,但是打印路径就不太方便。如果需要打印出二叉树的所有路径,可以使用下面的代码,暂时只有前序递归版本。

下面的代码输出结果是形如[ '1->2->4', '1->2->5', '1->3->6', '1->3->7' ]的字符串数组:

function binaryTreePathsString(root) {
  const paths = [];
  const construct_paths = (root, path) => {
    if (root) {
      path += root.val.toString();
      if (root.left === null && root.right === null) { // 当前节点是叶子节点
        paths.push(path); // 把路径加入到答案中
      } else {
        path += "->"; // 当前节点不是叶子节点,继续递归遍历
        construct_paths(root.left, path);
        construct_paths(root.right, path);
      }
    }
  }
  construct_paths(root, "");
  return paths
}

下面代码输出的结果是形如[ [ 1, 2, 4 ], [ 1, 2, 5 ], [ 1, 3, 6 ], [ 1, 3, 7 ] ]的数组:

function binaryTreePathsArray(root) {
    let paths = [];
    const resc = (root, path) => {
        if(root) {
            // path.push(root.val); 这样的写法是错误的
            // 数组是引用类型,跟上面代码的字符串是不一样的
            // 每次递归的时候都要浅拷贝一下
            path = [...path, root.val]; 
            if(root.left == null && root.right == null) {
                paths.push(path);
            } else {
                resc(root.left, path);
                resc(root.right, path);
            }
        }
    }
    resc(root, []);
    console.log(paths);
}

掌握上面的代码,下面的问题应该都能解决了:

剑指 Offer 68 - II. 二叉树的最近公共祖先
剑指 Offer 34. 二叉树中和为某一值的路径
124. 二叉树中的最大路径和

难度中等101收藏分享切换为英文接收动态反馈

层序遍历

简单来说就是一行一行地遍历,基于队列来做,先把根节点入队列,只要队列非空,每次把队头结点弹出,然后把堆头的左右节点压入队列中,这样最终遍历出来的就是层序遍历的顺序。

function levelOrder(root) {
    if (root == null)
        return null;
    let res = new Array();
    let queue = new Array();
    queue.unshift(root); // 先把根节点入队列
    while (queue.length > 0) { // 队列非空
        root = queue.pop();
        res.push(root.val); // 弹出队头节点
        if (root.left != null) queue.unshift(root.left);
        if (root.right != null) queue.unshift(root.right);
    }
    return res;
}

上面是一种比较简单的实现,只能按顺序进行遍历,例如[1, 2, 3, 4, 5, 6, 7],无法获取每一层的节点。

如果需要单独打印出每一层的节点,可以使用下面的写法:

function levelOrder(root) {
  if (root == null)
    return null;
  let res = new Array();
  let queue = new Array();
  queue.unshift(root);
  while (queue.length > 0) {
    let size = queue.length, // 队列保存了当前层的节点,获取节点个数
        temp = []; // 临时保存当前层节点的值
    for(let i=0; i<size; i++) { // for循环将当前层节点全部出队,并将下一层的节点加入队列
      root = queue.pop();
      temp.push(root.val);
      if (root.left != null) queue.unshift(root.left);
      if (root.right != null) queue.unshift(root.right);
    }
    res.push(temp);
  }
  return res
}

在上面的代码中,while每循环一次,就会遍历二叉树的一层,输出的结果为[ [ 1 ], [ 2, 3 ], [ 4, 5, 6, 7 ] ],掌握上面这个代码,下面的问题就不在话下了:

102. 二叉树的层序遍历
104. 二叉树的最大深度
111. 二叉树的最小深度
199. 二叉树的右视图
637. 二叉树的层平均值

参考:
二叉树遍历
二叉树:层序遍历登场!

查看原文

赞 0 收藏 0 评论 0

一杯绿茶 关注了专栏 · 10月9日

javascript-lNong

只此一生,何必从众

关注 1000

一杯绿茶 关注了专栏 · 10月9日

民工哥技术之路

公众号:民工哥技术之路、《Linux系统运维指南 从入门到企业实战》作者。专注系统架构、高可用、高性能、高并发,数据库、大数据、数据分析、Python技术、集群中间件、后端等开源技术分享。

关注 16079

一杯绿茶 关注了用户 · 10月9日

user_name @user__name

关注 255

一杯绿茶 关注了专栏 · 10月9日

终身学习者

我要先坚持分享20年,大家来一起见证吧。

关注 40749

一杯绿茶 关注了专栏 · 10月9日

springboot 最佳实践

SpringBoot技术的势、道、术分析与实践。

关注 554

一杯绿茶 关注了专栏 · 10月9日

code秘密花园

基础知识、算法、原理、项目、面试。公众号code秘密花园

关注 5200

一杯绿茶 关注了专栏 · 10月9日

web进阶

从前端菜鸟到全栈大牛的学习进阶之路

关注 734

一杯绿茶 关注了专栏 · 10月9日

SegmentFault 之声

在这里,我们将为你推送 SegmentFault 思否公司官方合作信息,和合作伙伴最新动态。SegmentFault 思否是中国领先的开发者社区和技术媒体,中国最大的 Hackathon 组织者。我们致力于成为科技企业和开发者沟通的桥梁,帮助科技企业和开发者对话。

关注 10132

认证与成就

  • 获得 0 次点赞
  • 获得 0 枚徽章 获得 0 枚金徽章, 获得 0 枚银徽章, 获得 0 枚铜徽章

擅长技能
编辑

(゚∀゚ )
暂时没有

开源项目 & 著作
编辑

(゚∀゚ )
暂时没有

注册于 8月15日
个人主页被 94 人浏览