Morris遍历树

[YBFACC]

Morris遍历

可以只使用O(1)空间完成树的遍历

核心就是子树的最右侧的节点的右指针指向父节点。

前序

var Morris_pre = function (root) {
  if (!root) return
  let curr = root
  while (curr) {
    if (curr.left) {
      let proNode = curr.left
      while (proNode.right && proNode.right !== curr) {
        proNode = proNode.right
      }
      if (!proNode.right) {
        console.log(curr.val)
        proNode.right = curr
        curr = curr.left
      } else {
        curr = curr.right
        proNode.right = null
      }
    } else {
      console.log(curr.val)
      curr = curr.right
    }
  }
}

中序

var Morris_mid = function (root) {
  if (!root) return
  let curr = root
  while (curr) {
    if (curr.left) {
      let proNode = curr.left
      while (proNode.right && proNode.right !== curr) {
        proNode = proNode.right
      }
      if (!proNode.right) {
        proNode.right = curr
        curr = curr.left
      } else {
        console.log(curr.val)
        curr = curr.right
        proNode.right = null
      }
    } else {
      console.log(curr.val)
      curr = curr.right
    }
  }
}

后序

有一个反转输出的过程

var Morris_post = function (root) {
  if (!root) return
  let curr = root
  while (curr) {
    if (curr.left) {
      let proNode = curr.left
      while (proNode.right && proNode.right !== curr) {
        proNode = proNode.right
      }
      if (!proNode.right) {
        proNode.right = curr
        curr = curr.left
        continue
      } else {
        proNode.right = null
        print(curr.left)
      }
    }
    curr = curr.right
  }
  print(root)
}

function print(node) {
  const tail = reverse(node)
  let temp = tail
  while (temp) {
    console.log(temp.val)
    temp = temp.right
  }
  reverse(tail)
}

function reverse(node) {
  let pre, next
  while (node) {
    ;[next, node.right] = [node.right, pre]
    ;[pre, node] = [node, next]
  }
  return pre
}

参考

JS中的二叉树遍历