二叉树展开为链表

[louzhedong]

习题

出处 LeetCode 算法第114题

给定一个二叉树，原地将它展开为链表。

例如，给定二叉树

    1
   / \
  2   5
 / \   \
3   4   6

将其展开为：

1
 \
  2
   \
    3
     \
      4
       \
        5
         \
          6

思路

采用递归的方式，每次递归返回头部和尾部的指针供后面使用

解答

var helper = function (root) {
  if (!root.left && !root.right) {
    return [root, root];
  }
  if (!root.left) {
    return [root, helper(root.right)[1]]
  }
  if (!root.right) {
    var temp = root.left;
    root.right = helper(temp)[0];
    root.left = null;
    return [root, helper(temp)[1]]
  }
  var temp = root.right;
  root.right = helper(root.left)[0];
  helper(root.left)[1].right = temp;
  root.left = null;
  return [root, helper(root.right)[1]]
}
var flatten = function (root) {
  if (!root) return null;
  helper(root);
};