二叉树展开为链表

Tips

题目类型: Tree

题目

给你二叉树的根结点 root, 请你将它展开为一个单链表: 展开后的单链表应该同样使用 TreeNode(即不能创建额外的树), 其中 right 子指针指向链表中下一个结点, 而左子指针始终为 null. 展开后的单链表应该与二叉树前序遍历顺序相同.

示例

输入:

     1
   /   \
  2     5
 / \     \
3   4     6

输出:

    1
     \
      2
       \
        3
         \
          4
           \
            5
             \
              6

题解

使用后序遍历, 从叶子节点开始向上处理, 将左子树"嫁接"到右子树. 这种方法不需要额外的空间.

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {void} Do not return anything, modify root in-place instead.
 */
var flatten = function (root) {
  if (!root) return

  flatten(root.left)
  flatten(root.right)

  const left = root.left
  const right = root.right

  root.left = null
  root.right = left

  let current = root
  while (current.right) {
    current = current.right
  }
  current.right = right
}