Leetcode 114 - Flatten binary tree to linked list

Note:

  • Use recursion with O(1) extra space.
  • Flatten left subtree first.
  • Let root.right = left.
  • Use tmp to get the last node of flattened left.
  • Let tmp.next = right.

Question:

Given the root of a binary tree, flatten the tree into a “linked list”:

  • The “linked list” should use the same TreeNode class where the right child pointer points to the next node in the list and the left child pointer is always null.
  • The “linked list” should be in the same order as a pre-order traversal of the binary tree.

Example:

img

1
2
Input: root = [1,2,5,3,4,null,6]
Output: [1,null,2,null,3,null,4,null,5,null,6]

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/**
* 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) {
construct(root);

function construct(node) {
if (!node) return null;
const leftSub = construct(node.left);
const rightSub = construct(node.right);
if (leftSub) {
node.left = null;
node.right = leftSub;
let tmp = node.right;
while (tmp.right) {
tmp = tmp.right;
}
tmp.right = rightSub;
} else {
node.right = rightSub;
}
return node;
}
};