- 微信
- 微博
  
  分享文章到微博
- 复制链接
  
  复制链接到剪贴板

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

Ustinian_2022 发表于 2022/08/06 20:58:30 2022/08/06

【摘要】将有序数组转换为二叉搜索树将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。本题中，一个高度平衡二叉树是指一个二叉树每个节点的左右两个子树的高度差的绝对值不超过 1。示例给定有序数组: [-10,-3,0,5,9],一个可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面这个高度平衡二叉搜索树： 0 / \ -3 ...

将有序数组转换为二叉搜索树

将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。本题中，一个高度平衡二叉树是指一个二叉树每个节点的左右两个子树的高度差的绝对值不超过 1。

示例

给定有序数组: [-10,-3,0,5,9],
一个可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面这个高度平衡二叉搜索树：
        0
     /      \
   -3       9
   / \     / \
 -10 null 5  null

方法一二分 + 递归法

思路

由于数组是按照递增有序排列的，并且高度平衡二叉搜索树（一个高度平衡二叉树是指一个二叉树每个节点的左右两个子树的高度差的绝对值不超过1），可以使用二分法从数组的中间开始查找数据。

详解

找出数组的中间坐标（mid）对应元素，作为当前二叉树节点（root）的 value
root 的左节点是 0 -> mid 的中间坐标对应元素
root 的右节点是 mid -> (arr.length - 1) 的中间坐标对应元素
root 的左右节点按照 1 - 3 步骤生成新的左右节点，直到数组遍历完，算法终止

代码

const sortedArrayToBST = (arr) => {
  return initTreeNodes(arr, arr.length - 1, 0);
};

const initTreeNodes = (arr, end, start) => {
  if (start <= end) {
    const mid = start + parseInt((end - start) / 2, 10);
    const root = Node(arr[mid]);
    root.left = initTreeNodes(arr, mid - 1, start);
    root.right = initTreeNodes(arr, end, mid + 1);
    return root;
  } else {
    return null;
  }
};

复杂度分析

时间复杂度：O(n)O(n)

每次调用需要遍历数组，因此，时间复杂度是 O(n)O(n)。
空间复杂度：O(1)O(1)

算法在运行过程中，只申请了常量大小内存，因此，空间复杂度是 O(1)O(1)。

方法二数组模拟队列

思路

可以先将提示数组按照二分法的查找顺数，一次推入数组中。然后，按照数组顺序通过生成二叉树的一般算法生成目标树。由于在题目的二叉树中，节点的左子节点的值要小于节点的值，节点的右子节点的值要大于节点的值。因此，数组从中点按照 [root, 左, 右, 左, 右…] 接收节点的值，并按照生成二叉树的一般算法，即可生成目标树。

详解

首先，使用二分法，先找到数组中间位置（mid）元素，将该元素 push 进目标数组 queue（模拟队列）
将数组分成两部分 0 -> mid, (mid + 1) -> arr.length
将获得两个新数组，按照 1、2 步骤重复，直到数组元素全部遍历完成
然后，按顺序遍历数组，arr[0]为根节点值
当 queue[i]，小于 arr[0] 时会被分配到左子节点，大于 arr[0] 时会被分配到右子节点
当左子节点已经有值时，会比较左子节点的值与 queue[i]，按照值得大小分配到左子节点的左子节点或者右子节点
当右子节点已经有值时，会比较右子节点的值与 queue[i]，按照值得大小分配到左子节点的左子节点或者右子节点
遍历 queue，重复执行 6、7 步骤，直到 queue 被全部遍历

代码

const sortedArrayToBST = (arr) => {
  if (!arr.length) {
    return null;
  }
  const queue = [];
  // 二分法重新排列数组 queue
  initNodeValueArr(arr, 0, arr.length, queue);
  // 根节点
  const root = new TreeNode(queue[0]);
  for (let i = 1; i < queue.length; i += 1) {
    // 插入节点数据
    insertNode(root, queue[i]);
  }
  return root;
};

const insertNode = (node, value) => {
  // 生成左子节点
  if (value < node.val) {
    if (!node.left) {
      node.left = new TreeNode(value);
    } else {
      insertNode(node.left, value);
    }
    // 生成右子节点
  } else if (!node.right) {
    node.right = new TreeNode(value);
  } else {
    insertNode(node.right, value);
  }
};

const initNodeValueArr = (arr, start, end, queue) => {
  const mid = start + parseInt((end - start) / 2, 10);
  queue.push(arr[mid]);
  // 左节点数值
  if (start < mid) {
    initNodeValueArr(arr, start, mid, queue);
  }
  // 右节点数值
  if (mid + 1 < end) {
    initNodeValueArr(arr, mid + 1, end, queue);
  }
};

复杂度分析

时间复杂度：O(n)O(n)

每次调用需要遍历数组，因此，时间复杂度是 O(n)O(n)。
空间复杂度：O(n)O(n)

算法在运行过程中，申请了 n 长度的数组 queue，因此，空间复杂度是 O(n)O(n)

对称二叉树、二叉树的最大深度和验证二叉搜索树

对称二叉树

给定一个二叉树，要判定是否是镜像对称的

示例

例如，二叉树 [1,2,2,3,4,4,3] 是对称的。

    1
   / \
  2   2
 / \ / \
3  4 4  3

但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:

    1
   / \
  2   2
     / \
    3   3

方法一递归判断

思路

判断二叉树是不是对称的，主要是看二叉树左边和右边的节点是不是各自相等。所以我们可以通过递归，去判断左树的左节点和右树的右节点是不是相同。如果两个节点都为空，则表示递归到树的底部了；如果有一边空了另外一半没空，说明有一边的节点没了，另外一半还在，肯定不是对称的树；如果两边对称，继续递归节点的左右节点，直到递归完全或者发现不对称。

详解

我们判断当前的树结构还是否为空，为空则该树是对称的，不为空则递归判断左子树的左子树和右子树的右子树是否相等
如果左节点或右节点为空时，则判断对应的右节点或左节点是否为空，为空则返回 true，不为空则返回 false
如果左右节点都不为空时，则判断左节点的左节点和右节点的右节点是否相等
如果相等，则继续传入该节点的子节点去判断；不相等则直接返回 false

代码

/**
 * 如果输入一个空对象，则直接返回true
 * @param {TreeNode} root
 * @return {boolean}
 */
const isSymmetric = function (root) {
  if (!root) {
    // 若根节点为空，则返回true
    return true;
  }
  // 递归函数
  return isSameTree(root.left, root.right);
};

/**
 * 判断二叉树是否对称，直接去判断根节点的左子树和右子树是否相同
 * @param {TreeNode} root
 */
const isSameTree = (r, l) => {
  // 若左节点或右节点为空，则判断对应的右节点或左节点是否为空
  // 为空时，则返回true，不为空则返回false
  if (r === null) return l === null;
  if (l === null) return r === null;

  // 判断左节点的左节点和右节点的右节点是否相等
  // 不相等时，则该树不对称，相等时则继续递归判断
  if (r.val !== l.val) return false;

  return isSameTree(r.left, l.right) && isSameTree(r.right, l.left);
};

复杂度分析

时间复杂度：O(n)O(n)

我们需要对这个树中的每个节点都要进行遍历
空间复杂度：O(n)O(n)

当树是线性时，由栈上的递归调用造成的空间复杂度为 O(n)O(n)

方法二迭代判断

思路

迭代的思路就是不断的把待处理的节点入队，每次都将本级的节点进行判断是否对称，如果不对称则返回false，对称则将下一级的节点全部入栈，然后再依次出队判断处理，再获取新的待处理节点入队，直到结束。

详解

最开始将根节点入列，然后新建一个出队的队列 level，我们对 level 进行判断处理。
我们一次取出 level 队列中下标为 i 和下标为 (level.length - i - 1) 的两个元素进行比较；
若不相等，则返回false；若相等，则将下下一级的节点全部入列，然后在将下一级的节点全部出列进行判断；
重复第 3、4 步，当队列为空时，则方法停止。

代码

/**
 * 如果输入一个空对象，则直接返回true
 * @param {TreeNode} root
 * @return {boolean}
 */
const isSymmetric = function (root) {
  if (!root) return true;
  const queue = [root.left, root.right];
  while (queue.length) {
    let len = queue.length;
    const level = [];
    while (len) {
      // 出列
      const pop = queue.shift();
      level.push(pop);
      if (pop) {
        // 入列
        queue.push(pop.left);
        queue.push(pop.right);
      }
      len--;
    }
    // 判断该层级的所有节点是否是对称的
    for (let i = 0, l = level.length; i < l / 2; i++) {
      // 一个为null，一个不为null的则该节点不对称
      // 返回fasle
      if (level[i] === null && level[l - i - 1] !== null) return false;
      if (level[i] !== null && level[l - i - 1] === null) return false;

      // 两个都不是null的情况
      // 节点不相等 返回false
      if (level[i] !== null && level[l - i - 1] !== null) {
        if (level[i].val !== level[l - i - 1].val) return false;
      }
    }
  }
  return true;
};

复杂度分析

时间复杂度：O(n)O(n)
空间复杂度：O(n)O(n)

当树是线性时，我们可能需要向队列中插入 O(n)O(n) 个节点

二叉树的最大深度

给定一个二叉树，找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。

示例

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

返回它的最大深度 3。

方法一递归查询排序

思路

遍历所有节点的深度，记录所有子节点的深度，然后筛选出最大的深度

详解

创建一个空数组用来保存所有节点深度
判断二叉树是否为空，空的直接返回 0，结束，非空二叉树继续
遍历二叉树节点，没有左右子节点的，直接将当前 level 塞入之前定义的深度数组
有左右子节点的就继续递归查询查询子节点的深度，传入的 level 也加 1 传递，直到二叉树遍历结束
对深度数组排序返回最大值，也就是二叉树最大深度

代码

const maxDepth = function (root) {
  // 创建保存节点深度的空数组
  const levelList = [];
  // 判断二叉树是否为空
  if (root === null) {
    return 0;
  } else {
    loop(root, 1);
    return sort(levelList);
  }
  // 遍历二叉树子节点
  function loop (node, level) {
    // 没有子节点的，将当前深度保存进深度数组，有节点的继续遍历
    if (node.left === null && node.right === null) {
      levelList.push(level);
    } else if (node.left !== null) {
      loop(node.left, level + 1);
    } if (node.right !== null) {
      loop(node.right, level + 1);
    }
  }

  // 对数组进行排序，返回最大深度
  function sort (arr) {
    arr.sort((a, b) => {
      return b - a;
    });
    return arr[0];
  }
};

复杂度分析

时间复杂度：O(n^2)O(n2)
空间复杂度：O(n)O(n)

方法二递归

思路

递归二叉树的节点，获取左子树和右子树的最大深度，比较后，返回最大深度

详解

判断二叉树是否为空，空的直接返回 0，结束，非空二叉树继续
分别递归计算左右子树的最大深度
根据返回两者的两者数字，比较后的返回二叉树的最大深度

代码

const maxDepth = function (root) {
  if (root === null) {
    return 0;
  } else {
    const leftDepth = maxDepth(root.left);
    const rightDepth = maxDepth(root.right);
    const childDepth = leftDepth > rightDepth ? leftDepth : rightDepth;
    return 1 + childDepth;
  }
};

复杂度分析

时间复杂度：O(n)O(n)

通过递归的方式查询了数的所有子节点。查询花费 O(n)O(n) 的时间。
空间复杂度：O(n)O(n)

每次递归都需要创建新的临时空间，空间复杂度 O(n)O(n)

二叉树的层次遍历、二叉树的序列化与反序列化和常数时间内插入删除、获得随机数

二叉树的层次遍历

给定一个二叉树，返回其按层次遍历的节点值。（即逐层地，从左到右访问所有节点）。

示例

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

    3
   / \
  9  20
    /  \
   15   7

返回其层次遍历结果：
[
  [3],
  [9,20],
  [15,7]
]

方法一递归

思路

最简单的解法就是递归，首先确认树非空，然后调用递归函数 helper(node, level)，参数是当前节点和节点的层次。

详解

输出列表称为 levels，当前最高层数就是列表的长度 len(levels)。比较访问节点所在的层次 level 和当前最高层次 len(levels) 的大小，如果前者更大就向 levels 添加一个空列表;
将当前节点插入到对应层的列表 levels[level] 中;
递归非空的孩子节点：helper(node.left / node.right, level + 1)。

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
const levelOrder = function (root) {
  const levels = [];
  if (!root) {
    return levels;
  }
  const helper = function (node, level) {
    if (levels.length === level) {
      levels.push([]);
    }
    levels[level].push(node.val);
    if (node.left) {
      helper(node.left, level + 1);
    }
    if (node.right) {
      helper(node.right, level + 1);
    }
  };
  helper(root, 0);
  return levels;
};

复杂度分析

时间复杂度：O(n)O(n)

因为每个节点恰好会被运算一次。
空间复杂度：O(n)O(n)

保存输出结果的数组包含 nn 个节点的值。

方法二迭代

思路

我们将树上顶点按照层次依次放入队列结构中，队列中元素满足 FIFO（先进先出）的原则。使用了 js 中的 push 和 shift 方法

第 0 层只包含根节点 root ，算法实现如下：

初始化队列只包含一个节点 root 和层次编号 0 ： level = 0。当队列非空的时候：

在输出结果 levels 中插入一个空列表，开始当前层的算法。
计算当前层有多少个元素：等于队列的长度。
将这些元素从队列中弹出，并加入 levels 当前层的空列表中。
将他们的孩子节点作为下一层压入队列中。
进入下一层 level++。

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
const levelOrder = function (root) {
  const levels = [];
  if (!root) {
    return levels;
  }

  let level = 0;
  const queue = [root];
  while (queue.length) {
    // 开始当前层级的循环
    levels.push([]);
    // 获取当前level的长度
    const levelLength = queue.length;

    for (let i = 0; i < levelLength; i++) {
      const node = queue.shift();
      // 给当前level添加值
      levels[level].push(node.val);

      // 给当前level添加子节点
      // 并加入队列，给下一个level使用
      if (node.left) {
        queue.push(node.left);
      }
      if (node.right) {
        queue.push(node.right);
      }
    }

    // 进入下一个level
    level += 1;
  }

  return levels;
};

复杂度分析

时间复杂度：O(n)O(n)
空间复杂度：O(n)O(n)

二叉树的序列化与反序列化

序列化是将一个数据结构或者对象转换为连续的比特位的操作，进而可以将转换后的数据存储在一个文件或者内存中，同时也可以通过网络传输到另一个计算机环境，采取相反方式重构得到原数据。

请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。

示例

你可以将以下二叉树：

    1
   / \
  2   3
     / \
    4   5

序列化为 "[1, 2, 3, null, null, 4, 5]"

方法一深度优先遍历(DFS)

思路

遍历二叉树：L、D、R 分别表示遍历左子树、访问根结点和遍历右子树。先序遍历二叉树的顺序是 DLR，中序遍历二叉树的顺序是 LDR，后序遍历二叉树的顺序是 LRD。深度优先遍历包含先序、中序、后序遍历。先序遍历的顺序：先访问根节点，再遍历左节点，最后遍历右节点。为了能够反序列化，在遍历的时候需要将 null 也保存进去。伪代码如下：

你可以将以下二叉树：

    1
   / \
  2   3
     / \
    4   5

序列化为 "[1, 2, 3, null, null, 4, 5]"

示例中的二叉树以本算法先序遍历后的结果为：[1,2,null,null,3,4,null,null,5,null,null] 反序列化：将先序遍历的结果按根节点、左子树、右子树顺序复原，伪代码如下：

  structure();
  node = new TreeNode();
  node.left = structure();
  node.right = structure();

详解

首先序列化二叉树，定义一个遍历方法，先访问根节点，再遍历左节点，最后遍历右节点，将 null 也保存进数组中
反序列化二叉树，将数组还原回二叉树，因为数组是先序遍历的结果，遍历数组，然后按照根节点、左子树、右子树顺序复原二叉树

/**
 * 二叉树节点构造函数
 * @param {string} val 节点值
 */
function TreeNode (val) {
  this.val = val;
  this.left = this.right = null;
}

/**
 * 序列化二叉树，将二叉树转成数组
 * @param {TreeNode} root
 */
const serialize = function (root) {
  const result = [];
  // 遍历节点
  function traverseNode (node) {
    if (node === null) {
      result.push(null);
    } else {
      // 先序遍历，先访问根节点，再遍历左节点，最后遍历右节点
      result.push(node.val);
      traverseNode(node.left);
      traverseNode(node.right);
    }
  }

  traverseNode(root);
  return result;
};

/**
 * 反序列化二叉树，将数组还原回二叉树
 * @param {string} data
 */
const deserialize = function (data) {
  const length = data.length;
  if (length === 0) {
    return null;
  }
  let i = 0;
  // data 结构化成树
  function structure () {
    if (i >= length) {
      return null;
    }
    const val = data[i];
    i++;
    if (val === null) {
      return null;
    }
    const node = new TreeNode(val);
    node.left = structure();
    node.right = structure();

    return node;
  }
  return structure();
};

复杂度分析

时间复杂度：O(n)O(n)
空间复杂度：O(n)O(n)

serialize 方法为 result 分配了空间，递归中没有产生新的对象，空间复杂度为 O(1)O(1) deserialize 方法每次遍历会 new 一个对象，空间复杂度为 O(n)O(n)

方法二广度优先遍历(BFS)

示例中的二叉树以本算法广度优先(层序)遍历后的结果为：[1,2,3,null,null,4,5]

思路

序列化：广度优先遍历序列化二叉树是按层级从上往下将每层节点从左往右依次遍历，用队列来处理遍历，先将根节点入队，然后根节点出队，再左子树和右子树入队，递归遍历即可。反序列化：从序列化好的数组中取第一个元素，生成根节点。将根节点放入队列。循环队列，根节点的左右子树分别放入队列，循环此操作，直到队列为空。

详解

序列化： 1. 定义一个 result 数组存放序列化结果 1. 定义一个 queue 数组，作为队列 2. 将根节点入队 3. 循环队列，队列中的第一个元素(节点)出队，将此节点值 push 进 result 数组。分别将此节点左右节点入队 4. 当队列为空时，跳出循环 5. 返回 result

反序列化： 1. 从 result 取出第一个节点值，生成根节点放到队列中 2. 循环队列，队列中第一个元素(节点)出队，从 result 取出下一个值还原左节点，将此左节点入队，从 result 取出下一个值还原右节点，将此右节点入队 3. 当 result 或队列为空时，跳出循环 4. 返回反序列化好的节点(根节点)

/**
 * 二叉树节点构造函数
 * @param {string} val 节点值
 */
function TreeNode (val) {
  this.val = val;
  this.left = this.right = null;
}

/**
 * 序列化二叉树，将二叉树转成数组
 * @param {TreeNode} root
 */
const serialize = function (root) {
  if (!root) {
    return [];
  }
  const result = [];
  const queue = [];
  queue.push(root);
  let node;
  while (queue.length) {
    node = queue.shift();
    result.push(node ? node.val : null);
    if (node) {
      queue.push(node.left);
      queue.push(node.right);
    }
  }
  return result;
};

/**
 * 反序列化二叉树，将数组还原回二叉树
 * @param {string} data
 */
const deserialize = function (data) {
  const length = data.length;
  if (length === 0) {
    return null;
  }
  // 取出第一个节点值，生成根节点放到队列中
  const root = new TreeNode(data.shift());
  const queue = [root];
  while (queue.length) {
    // 取出将要复原的节点
    const node = queue.shift();
    // 节点遍历完，跳出循环
    if (data.length === 0) {
      break;
    }
    // 先还原左节点
    const leftVal = data.shift();
    if (leftVal === null) {
      node.left = null;
    } else {
      node.left = new TreeNode(leftVal);
      // 将生成的左节点放入队列，下次循环会复原此左节点的子节点
      queue.push(node.left);
    }
    // 节点遍历完，跳出循环
    if (data.length === 0) {
      break;
    }
    // 还原右节点
    const rightVal = data.shift();
    if (rightVal === null) {
      node.right = null;
    } else {
      node.right = new TreeNode(rightVal);
      // 将生成的右节点放入队列，下次循环会复原此左节点的子节点
      queue.push(node.right);
    }
  }

  return root;
};

复杂度析

时间复杂度：O(n)O(n)

serialize 方法中每个节点遍历一次，时间复杂度为 O(n)O(n) deserialize 方法遍历 nn 次，nn 为 data 的长度，时间复杂度为 O(n)O(n)
空间复杂度：O(n)O(n)

serialize 方法为 result 分配了空间，递归中没有产生新的对象，空间复杂度为 O(1)O(1)deserialize 方法每次遍历会 new 一个对象，空间复杂度为 O(n)O(n)

点赞
收藏
关注作者

0/1000

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

全部回复

上滑加载中

设置昵称

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

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

确认取消

加入云驻计划，成为创作者

华为云周边好礼
免费体验产品
特殊身份标识
线下官方门票
内部专家零距离
与10000+优质创作者共同成长

立即加入

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

将有序数组转换为二叉搜索树

方法一二分 + 递归法

方法二数组模拟队列

对称二叉树、二叉树的最大深度和验证二叉搜索树

对称二叉树

方法一递归判断

方法二迭代判断

二叉树的最大深度

方法一递归查询排序

方法二递归

二叉树的层次遍历、二叉树的序列化与反序列化和常数时间内插入删除、获得随机数

二叉树的层次遍历

方法一递归

方法二迭代

二叉树的序列化与反序列化

方法一深度优先遍历(DFS)

方法二广度优先遍历(BFS)

全部回复

设置昵称

关于作者

目录

加入云驻计划，成为创作者

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

将有序数组转换为二叉搜索树

方法一 二分 + 递归法

方法二 数组模拟队列

对称二叉树、二叉树的最大深度和验证二叉搜索树

对称二叉树

方法一 递归判断

方法二 迭代判断

二叉树的最大深度

方法一 递归查询排序

方法二 递归

二叉树的层次遍历、二叉树的序列化与反序列化和常数时间内插入删除、获得随机数

二叉树的层次遍历

方法一 递归

方法二 迭代

二叉树的序列化与反序列化

方法一 深度优先遍历(DFS)

方法二 广度优先遍历(BFS)

全部回复

设置昵称

关于作者

目录

加入云驻计划，成为创作者

推荐阅读

相关产品

方法一二分 + 递归法

方法二数组模拟队列

方法一递归判断

方法二迭代判断

方法一递归查询排序

方法二递归

方法一递归

方法二迭代

方法一深度优先遍历(DFS)

方法二广度优先遍历(BFS)