中序遍历JS非递归版

二叉搜索树与双向链表

http://www.nowcoder.com/questionTerminal/947f6eb80d944a84850b0538bf0ec3a5

/**
 * 将二叉搜索树转换成双向链表,不能新增节点,只能修改原有节点
 * left 表示链表的上一个节点,right 表示下一个节点
 * 
 * 思路:
 * 中序遍历二叉树,用 pre 保存上一个遍历到的节点即可
 * 
 * @param {Node} head 
 */

function Convert(head)
{
  if(!head) return null
  let stack = []
  let node = head
  let newHead = null
  let pre = null
  while(stack.length || node) {
    if(node) {
      stack.push(node)
      node = node.left
    } else {
      node = stack.pop()

      // 保存链表头
      if(!newHead) newHead = node

      // 改变节点指向
      if(pre) {
        pre.right = node
        node.left = pre
      }

      pre = node
      node = node.right
    }
  }
  return newHead
}
全部评论

相关推荐

快点约我面试吧
投递百度等公司10个岗位
点赞 评论 收藏
分享
喝干太平洋:我是大专 我感觉我当时的简历比你好点 就一个vue吗
点赞 评论 收藏
分享
Java大菜狗:纯纯招黑奴,一天还不到两百那么多要求,还不迟到早退,以为啥啊,给一点工资做一堆活,还以不拖欠员工工资为荣,这是什么值得骄傲的事情吗,纯纯***公司
点赞 评论 收藏
分享
评论
点赞
1
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务