LeetCode题解:897. 递增顺序搜索树,栈,JavaScript,详细注释

2021/9/7 9:06:16

本文主要是介绍LeetCode题解:897. 递增顺序搜索树,栈,JavaScript,详细注释,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

原题链接:897. 递增顺序搜索树

解题思路:

  1. 使用中序遍历,即可按顺序获取到二叉搜索树的每个节点。

  2. 创建一个新树,用leaf表示其叶子节点。

  3. 每次遍历到节点时,都进行如下操作:

    • 将遍历到的节点连接到leaf.right
    • leaf移动到leaf.right,保持它一直指向叶子节点。
    • leaf.left设置为null,打断节点原有的连接,避免新树出现环。
/**
 * @param {TreeNode} root
 * @return {TreeNode}
 */
var increasingBST = function (root) {
  let dummy = new TreeNode() // 创建一个虚拟节点,dummy.right指向新树的根节点
  let leaf = dummy // 创建leaf节点,其指向新树的叶子节点,初始值为dummy
  let stack = [] // 使用栈辅助遍历
  let current = root // 使用节点进行遍历

  // 中序遍历二叉树
  // 遍历的过程中,可能出现current为空,而stack中有元素,即为遍历到树的最底端。
  // 也可能出现current有值而stack为空的情况,如遍历到二叉树的根节点。
  while (stack.length || current) {
    // 不断向左下遍历节点,同时将所有节点入栈
    // 这样就保证了总是从最左端开始遍历节点
    while (current) {
      stack.push(current)
      current = current.left
    }

    // 从栈中弹出节点,即为当前遍历的节点
    // 弹出节点的顺序为从左到右。
    const node = stack.pop()

    // 处理中序遍历读取到的节点
    // 将当前节点都连接到叶子节点的右子节点
    leaf.right = node
    // 将leaf向右子节点移动,用于连接下一个节点
    leaf = leaf.right
    // 将left设置为null,打断节点原有的连接,避免新树出现环
    leaf.left = null

    // 不断向右侧遍历树,如果右侧节点为空,则会从栈中弹出当前子树的根节点
    // 这样就形成了从左到右的遍历顺序
    current = node.right
  }

  // dummy.right指向的是新树的根节点
  return dummy.right
}


这篇关于LeetCode题解:897. 递增顺序搜索树,栈,JavaScript,详细注释的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程