101道算法JavaScript描述【二叉树】7

举报
Ustinian_2022 发表于 2022/08/06 21:04:50 2022/08/06
【摘要】 填充每个节点的下一个右侧节点指针、岛屿数量和二叉树的锯齿形层次遍历 填充每个节点的下一个右侧节点指针给定一个完美二叉树,其所有叶子节点都在同一层,每个父节点都有两个子节点。二叉树定义如下:struct Node { int val; Node *left; Node *right; Node *next;}填充它的每个 next 指针,让这个指针指向其下一个右侧节点。如果找不到下一...

填充每个节点的下一个右侧节点指针、岛屿数量和二叉树的锯齿形层次遍历

填充每个节点的下一个右侧节点指针

给定一个完美二叉树,其所有叶子节点都在同一层,每个父节点都有两个子节点。二叉树定义如下:

struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}

填充它的每个 next 指针,让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点,则将 next 指针设置为 NULL。 初始状态下,所有 next 指针都被设置为 NULL

示例

输入:{"$id":"1","left":{"$id":"2","left":{"$id":"3","left":null,"next":null,"right":null,"val":4},"next":null,"right":{"$id":"4","left":null,"next":null,"right":null,"val":5},"val":2},"next":null,"right":{"$id":"5","left":{"$id":"6","left":null,"next":null,"right":null,"val":6},"next":null,"right":{"$id":"7","left":null,"next":null,"right":null,"val":7},"val":3},"val":1}

输出:{"$id":"1","left":{"$id":"2","left":{"$id":"3","left":null,"next":{"$id":"4","left":null,"next":{"$id":"5","left":null,"next":{"$id":"6","left":null,"next":null,"right":null,"val":7},"right":null,"val":6},"right":null,"val":5},"right":null,"val":4},"next":{"$id":"7","left":{"$ref":"5"},"next":null,"right":{"$ref":"6"},"val":3},"right":{"$ref":"4"},"val":2},"next":null,"right":{"$ref":"7"},"val":1}

解释:给定二叉树如图 A 所示,你的函数应该填充它的每个 next 指针,以指向其下一个右侧节点

提示

  • 你只能使用常量级额外空间。
  • 使用递归解题也符合要求,本题中递归程序占用的栈空间不算做额外的空间复杂度。

方法一 递归法

思路

使用树的先序遍历(递归方式)。这里需要解决两种情形,第一,同一父节点的左右节点的连接,如图中的 23 节点;第二,相近但非同一直系父节点的节点相连,如图中的 56 节点。

详解

  1. 第一步,同一父节点的左右节点的连接:先将同一父节点的左节点的 next 指向右节点,以图例中的节点 1 为例,其左节点 2next 指向右节点 3
  2. 第二步,相近但非同一直系父节点的节点相连:考虑到不同直系父节点的同一层节点也需要相连,以图例中的节点 56 为例,5next 指向 6。我们可以通过 5 的父节点 2next 节点找到 3,再通过节点 3,找到节点 6,即访问节点 3 的左节点。以此类推,无论下面还有多少层,都可以通过这种方法,连接相近但不是同一直系父节点的两个子节点。

代码

/**
 * // Definition for a Node.
 * function Node(val, left, right, next) {
 *    this.val = val === undefined ? null : val;
 *    this.left = left === undefined ? null : left;
 *    this.right = right === undefined ? null : right;
 *    this.next = next === undefined ? null : next;
 * };
 */
/**
 * @param {Node} root
 * @return {Node}
 */
const connect = (root) => {
  // 递归出口
  if (root === null) {
    return root;
  }
  // 同一父节点的左右节点相连,如图中 2、3 节点相连
  if (!!root.left && !!root.right) {
    root.left.next = root.right;
  }
  // 相近但非同一直系父节点的节点相连,如图中 5、6 节点相连
  if (!!root.right && root.next && root.next.left) {
    root.right.next = root.next.left;
  }
  connect(root.left);
  connect(root.right);
  return root;
};

复杂度分析

  • 时间复杂度:O(n)O(n)

    上述解法中,树的每个节点只访问了一次,时间复杂度跟树的节点个数线性相关,因此为 O(n)O(n)。

  • 空间复杂度:O(1)O(1)

    由于题目提示中声明,递归程序占用的栈空间不算做额外的空间复杂度,因此为 O(1)O(1)。

方法二 层序遍历法(队列方式)

思路

使用层序遍历的方法,每一层按从左到右进行遍历,把遍历出来的节点依次连接起来,但在连接的时候需要注意,每层的最后一个节点的 next 需要置为 null,而不是和前一个节点相连。

详解

  1. 第一步,进行二叉树的层序遍历,每一层按从左到右进行遍历,把遍历出来的节点依次连接起来。 补充说明:如何进行二叉树的层序遍历?核心思想是使用队列先进先出的特性。 以上述示例图中的二叉树为例。首先初始化,将根节点 1 推入队列,然后,首位(即节点 1)出队列,并将其左子节点 2 和右子节点 3 推入队列,然后,首位(即节点 2)出队列,并将其左子节点 4 和右子节点 5 推入队列,接下去,节点 3 出队列,节点 4 5 入队列,依次类推,直到队列为空,二叉树遍历结束。
  2. 第二步,在连接的时候,判断当前遍历到的节点是否为该层的最右节点。具体判断方法如下:因为层序遍历过程中,队列的 size 即为当前层节点的总个数,使用 for 循环进行当前层的遍历,循环执行的最后一次就是该层最后一个节点。
/**
 * // Definition for a Node.
 * function Node(val, left, right, next) {
 *    this.val = val === undefined ? null : val;
 *    this.left = left === undefined ? null : left;
 *    this.right = right === undefined ? null : right;
 *    this.next = next === undefined ? null : next;
 * };
 */
/**
 * @param {Node} root
 * @return {Node}
 */
const connect = (root) => {
  const arr = [];
  if (root === null) {
    return root;
  }
  arr.push(root);
  while (arr.length) {
    // size 为每一层节点的总个数。 prevNode 记录前一个节点。
    const size = arr.length;
    let prevNode;
    let node;
    // 遍历每一层的节点
    for (let i = 0; i < size; i += 1) {
      node = arr.shift(); // 出队列
      // 每一层最后一个节点的 next 需要置为 null
      // 因此,当前节点不是当前层的最后一个节点的话,将当前节点与前一节点连接
      if (prevNode && i < size) {
        prevNode.next = node;
      }
      if (node.left) {
        arr.push(node.left); // 左节点入队列
      }
      if (node.right) {
        arr.push(node.right); // 右节点入队列
      }
      prevNode = node;
    }
  }
  return root;
};

复杂度分析

  • 时间复杂度:O(n)O(n)

    上述解法中,树的每个节点只访问了一次,时间复杂度跟树的节点个数线性相关,因此为 O(n)O(n)。

  • 空间复杂度:O(n)O(n)

    由于解法中使用到队列,且在访问最下面一层叶子节点时,空间占用达到最大,即存储了 (n+1)/2(n+1)/2 个节点,因此为 O(n)O(n)。

方法三 层序遍历法(指针方式)

思路

使用 2 个指针 startcurrent 来进行层序遍历。其中 start 用于标记每一层的第一个节点,current 用来遍历该层的其他节点。

详解

  1. 第一步,定义一个 start 指针,用于标记每一层的第一个节点,start 指针的初始化值为 root 节点,只需要 start = start.left,就能获取到每一层的第一个节点。
  2. 第二步,定义一个 current 指针,用来遍历该层的其他节点。然后,将同一父节点的左右节点的连接,即current.left.next = current.right,如图中的 23 节点;将相近但非同一直系父节点的节点相连,即current.right.next = current.next.left,如图中的 56 节点。

代码

/**
 * // Definition for a Node.
 * function Node(val, left, right, next) {
 *    this.val = val === undefined ? null : val;
 *    this.left = left === undefined ? null : left;
 *    this.right = right === undefined ? null : right;
 *    this.next = next === undefined ? null : next;
 * };
 */
/**
 * @param {Node} root
 * @return {Node}
 */
const connect = (root) => {
  if (root === null) {
    return root;
  }
  let start = root;
  let current = null;
  // start 为每一层的第一个节点
  while (start.left) {
    // 每一层节点的遍历
    current = start;
    while (current) {
      // 同一父节点的左右节点相连,如图中 2、3 节点相连
      current.left.next = current.right;
      // 相近但非同一直系父节点的节点相连,如图中 5、6 节点相连
      if (current.next) {
        current.right.next = current.next.left;
      }
      current = current.next;
    }
    start = start.left;
  }
  return root;
};

复杂度分析

  • 时间复杂度:O(n)O(n)

    本解法中,外层循环总共执行 k 次(其中 k 为树的最大深度),内层循环根据所在的层次不同而不同,第一层1次,第二层 2 次,第 k 层 2^{k-1}2k−1 次,而 1+2+…(2^{k-1})=n1+2+…(2k−1)=n,即所有节点数之和,因此时间复杂度为 O(n)O(n)。

  • 空间复杂度:O(1)O(1)

    由于解法中只申请了 2 个变量,空间复杂度与树的节点个数 n 无关,因此为 O(1)O(1)。

岛屿数量

给定一个由 ‘1’(陆地)和 ‘0’(水)组成的的二维网格,计算岛屿的数量。一个岛被水包围,并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。

示例 1:

输入:
11110
11010
11000
00000

输出: 1

示例 2:

输入:
11000
11000
00100
00011

输出: 3

方法一 深度优先遍历

思路

遍历二维数组,当节点为陆地(1)时,对当前节点的上下左右四个方向启动深度优先遍历搜索,并将计数器加 1。同时在搜索过程中,遇到海水(0)节点便停止,遇到陆地(1)节点便标记为海水(0)节点。

详解

  1. 定义岛屿数量计数变量 landNum
  2. 对二维数组 grid 进行两层遍历
  3. 遍历过程中,遇到为 1 的陆地则将 landNum 自增 1,然后进入传播函数,并传入当前的坐标 ij
  4. 根据传入的坐标,判断是否超出 grid 边界,并判断是否为 0
  5. 若为超出边界,或为 0,则停止传播
  6. 若为边界内的 1,则将该位置变为 0,并对此节点的上下左右节点继续递归传播,以此实现深度优先遍历
  7. 传播结束后,便可根据 landNum 获得岛屿数量

代码

/**
 * @param {character[][]} grid
 * @return {number}
 */
var numIslands = function(grid) {
  let landNum = 0

  for(let i = 0; i < grid.length; i++) {
        const len = grid[i].length;
        for(let j = 0; j < len; j++) {
            const target = grid[i][j]
            if (target === '1') {
                spread(grid, i, j)
                landNum++
            }
        }
  }
  return landNum;
};

/**
 * @param {character[][]} grid
 * @param {number} i
 * @param {number} j
 */
function spread(grid, i, j) {
  if (i < 0 || j < 0 || i >= grid.length || j >= grid[i].length || grid[i][j] !== '1') {
        return
  }

  grid[i][j] = '0'
  spread(grid, i, j + 1);
  spread(grid, i, j - 1);
  spread(grid, i + 1, j);
  spread(grid, i - 1, j);
}

复杂度分析

  • 时间复杂度:O(n)O(n)

    n 为传入的二维网络的节点个数

  • 空间复杂度:O(n)O(n)

    最坏情况下为 O(n)O(n),此时整个网格均为陆地

方法二 广度优先遍历

思路

遍历二维数组,当节点为陆地(1)时,启动广度优先遍历搜索,将节点坐标放入队列中,并将计数器加 1。在搜索过程中,遇到陆地(1)节点便标记为海水(0)节点,迭代搜索队列中的每个结点,直到队列为空。

详解

  1. 定义岛屿数量计数变量 landNum
  2. 对二维数组 grid 进行两层遍历
  3. 遍历过程中,遇到为 1 的陆地则将 landNum 自增 1,然后进入传播函数,并传入当前的坐标 ij
  4. 根据传入的坐标,构造成 queue 队列数组
  5. 循环判断 queue 的数组长度
  6. 若数组中存在坐标,则将末尾坐标从 queuepop 取出
  7. 判断取出的坐标是否为边界内的 1,若是,则将此坐标设置为 0,并将此坐标的上下左右坐标存入 queue 数组中,以此完成广度优先遍历
  8. 遍历结束后,便可根据 landNum 获得岛屿数量

代码

/**
 * @param {character[][]} grid
 * @return {number}
 */
var numIslands = function(grid) {
    let landNum = 0

  for(let i = 0; i < grid.length; i++) {
        const len = grid[i].length;
        for(let j = 0; j < len; j++) {
            const target = grid[i][j]
            if (target === '1') {
                spread(grid, i, j)
                landNum++
            }
        }
    }

  return landNum;
};


/**
 * @param {character[][]} grid
 * @param {number} i
 * @param {number} j
 */
function spread(grid, i, j) {
  const queue = [[i, j]]

  while (!!queue.length) {
        const [i, j] = queue.pop()
        if (grid.length > i 
            && i >= 0
            && grid[0].length > j
            && j >= 0
            && grid[i][j] === '1') {

            grid[i][j] = '0'
            queue.push([i - 1, j])
            queue.push([i + 1, j])
            queue.push([i, j + 1])
            queue.push([i, j - 1])
        }
    }
}

复杂度分析

  • 时间复杂度:O(n)O(n)

    n 为传入的二维网络的节点个数

  • 空间复杂度:O(n)O(n)

    最坏情况下为 O(n)O(n),此时整个网格均为陆地

二叉树的锯齿形层次遍历

给定一个二叉树,返回其节点值的锯齿形层次遍历。(即先从左往右,再从右往左进行下一层遍历,以此类推,层与层之间交替进行)。

示例

给定二叉树 [3, 9, 20, null, null, 15, 7],

    3
   / \
  9  20
    /  \
   15   7

返回锯齿形层次遍历如下:

[
  [3],
  [20,9],
  [15,7]
]

方法一 双栈法

思路

栈:是一种数据结构,先进后出原则。

双栈法:

  1. 定义两个数组,一个接收奇数层元素,另一个接收偶数层元素。
  2. 奇数层遍历完成之后,将下一层元素由左向右插入偶数层数组。
  3. 先进后出原则,偶数列遍历时,取值顺序就变成了由右向左取值。
  4. 偶数层遍历完成之后,将下一层元素由右向左插入奇数层数组。
  5. 先进后出原则,奇数列遍历时,取值顺序就变成了由左向右取值。
  6. 循环往复,形成锯齿形层次遍历

详解

  1. 定义结果数组
  2. 定义两个数组模拟栈(l2r、r2l),一个由左向右,一个由右向左
  3. 将要处理的数据 push 到 l2r,进行循环
  4. 每层循环定义一个 临时数组,接收当前层的结果,最后需要 push 到结果数组。
  5. 第一层 l2r 就一个根数据,直接就将当前值 push 到 临时数组。为了方便交替遍历,将 l2r 的下一层数据 由左向右 push 到 r2l
  6. 第二层 r2l 的数据是由左向右,先进后出,所以我们循环取值是 由右向左,将当前结果 push 到 临时数组,然后将 r2l 的下一层数据 由右向左 push 到 l2r
  7. 循环往复

代码

const zigzagLevelOrder = function (root) {
  if (!root) return [];
  const res = [];
  const l2r = [];
  const r2l = [];
  l2r.push(root);
  while (l2r.length || r2l.length) {
    const temp = [];
    if (l2r.length) {
      while (l2r.length) {
        const cur = l2r.pop();
        temp.push(cur.val);
        if (cur.left) r2l.push(cur.left);
        if (cur.right) r2l.push(cur.right);
      }
    } else if (r2l.length) {
      while (r2l.length) {
        const cur = r2l.pop();
        temp.push(cur.val);
        if (cur.right) l2r.push(cur.right);
        if (cur.left) l2r.push(cur.left);
      }
    }
    res.push(temp);
  }
  return res;
};

复杂度分析

  • 时间复杂度:O(n)O(n)

    每个节点都要进栈和出栈,所以时间复杂度为 O(n)O(n)

  • 空间复杂度:O(n)O(n)

    双栈每个节点的值也只记录一次,所以空间复杂度为 O(n)O(n)

方法二 递归

思路

采用递归,一层层遍历。每一层创建一个数组,奇数层元素从左向右插入数组,偶数层元素从右向左插入数组。

& 与操作符 判断奇偶

详解

  1. 先在最层城定义返回结果数组
  2. 然后看递归方法
    1. 定义两个参数。第一个 i 层数减一,对应返回结果数组的索引值;第二个 current ,当前处理对象;
    2. 首先判断结果数组当前索引的是否为第一次创建,不是创建新数组
    3. 索引为奇数,对应树形结构偶数行,从右向左插入
    4. 索引为偶数,对应树形结构奇数行,从左向右插入
    5. 然后不断递归

代码

const zigzagLevelOrder = function (root) {
  const res = [];
  dfs(0, root);
  return res;
  function dfs (i, current) {
    if (!current) return;
    // 首次进入该层递归,现在结果创建新数组用来接收结果。
    if (!Array.isArray(res[i])) res[i] = [];
    // 判断当前层数索引奇偶
    // 奇数从前插入数组,偶数从后插入数组
    if (i & 1) res[i].unshift(current.val);
    else res[i].push(current.val);
    // 左侧子二叉树进入递归
    dfs(i + 1, current.left);
    // 右侧子二叉树进入递归
    dfs(i + 1, current.right);
  }
};

复杂度分析

  • 时间复杂度:O(n)O(n)

    因为每个节点恰好会被运算一次

  • 空间复杂度:O(n)O(n)

    系统栈需要记住每个节点的值,所以空间复杂度为 O(n)O(n)

【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。