-
Notifications
You must be signed in to change notification settings - Fork 4
/
populating-next-right-pointers-in-each-node-ii.js
64 lines (57 loc) · 5.17 KB
/
populating-next-right-pointers-in-each-node-ii.js
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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
var DEBUG = process.env.DEBUG;
/**
* Definition for binary tree with next pointer.
**/
function TreeLinkNode(val) {
this.val = val;
this.left = this.right = this.next = null;
}
function nextLevelLeftmost(node, r) {
while (node && node !== r) {
if (node.left) {
return node.left;
} else if (node.right) {
return node.right;
} else {
node = node.next;
}
}
if (node === r) return null;
return node;
}
function merge(node) {
if (!node.left || !node.right) return;
var l = node.left;
var r = node.right;
while (l && r) {
var rightmostofl = l;
while (rightmostofl && rightmostofl.next) {
rightmostofl = rightmostofl.next;
}
rightmostofl.next = r;
l = nextLevelLeftmost(l, r);
r = nextLevelLeftmost(r);
}
}
/**
* @param {TreeLinkNode} root
* @return {void} Do not return anything, modify tree in-place instead.
*/
var connect = function(root) {
if (!root) return ;
connect(root.left);
connect(root.right);
merge(root);
};
function test(f) {
var buildTree = require('./treeUtils').buildTree;
[
{val: 1, left: {val: 2}, right: {val: 3} },
buildTree([3,9,20,'#','#',15,7], TreeLinkNode),
buildTree([100,-69,-73,-138,-14,51,256,118,-193,231,120,-175,34,135,-59,0,-2,128,143,-131,238,173,201,-18,-153,-160,241,183,-173,165,240,-121,224,-135,-4,'#',21,-156,289,171,64,95,-137,223,-37,-12,17,74,-172,-7,18,210,174,62,267,243,145,10,24,-56,-129,'#',163,'#',248,'#','#',-60,228,-84,54,105,291,'#',45,157,-93,-198,-163,14,166,97,93,-46,76,-1,30,'#',176,192,-36,270,-17,-180,216,194,144,156,-48,110,37,'#',59,-102,28,'#',221,124,286,65,-119,'#',-61,131,'#',55,249,-143,'#',273,287,'#','#',-88,'#',1,282,-113,-77,'#',-51,-104,90,'#','#',81,-90,259,298,195,-192,96,251,20,-28,-21,-101,214,-132,-35,-8,-49,-40,'#','#','#','#',158,-38,-178,47,'#',191,'#','#',12,'#',142,'#','#',279,-161,'#','#','#',-95,-127,295,119,-134,-194,'#',57,-141,'#','#',84,261,85,-115,'#','#','#','#',186,'#','#',146,'#','#',112,254,8,'#','#','#','#',89,277,98,280,'#',-149,'#','#',-123,180,123,'#','#','#',7,-29,212,3,263,-13,-81,'#',296,276,'#',-189,'#','#','#','#',-151,'#',-155,175,77,-185,91,-162,-30,121,189,-168,169,-142,'#','#','#','#',-100,140,-42,32,'#','#','#','#',109,'#',-11,168,232,49,-3,-65,108,'#','#','#','#','#',178,233,-112,87,'#','#','#',41,'#','#','#','#',-147,'#',-80,'#','#',13,-154,-128,-106,127,'#','#','#',284,274,'#','#','#',88,294,-53,-64,-196,'#','#',-23,-199,'#','#','#',31,'#',-182,'#','#',-83,'#','#','#','#',-20,35,'#',244,-191,-120,141,-54,'#','#',293,'#',46,-62,-200,52,208,-140,'#',-24,-170,-45,-33,-118,'#',172,'#','#',-82,129,'#','#',-107,-16,'#','#','#',196,-32,-186,2,'#',-79,'#',177,269,-139,-158,'#','#',-150,-152,134,'#',-111,'#',103,'#',-126,6,'#','#','#','#','#',187,70,-116,211,167,-183,'#','#','#','#',11,'#',227,126,'#','#','#',94,'#',197,5,'#',153,'#',-5,257,'#','#','#',150,-78,'#','#','#','#',-9,-195,'#','#','#','#',38,'#',154,236,'#','#',-99,-63,'#',253,'#','#','#','#','#','#','#','#','#','#','#','#','#','#','#','#','#','#',226,'#',133,198,'#',132,'#','#','#',40,148,'#',-177,'#',288,-96,'#',71,'#',-94,'#',255,15,164,'#',-91,69,39,'#','#','#','#','#','#','#',-74,'#',-66,'#','#',-179,107,'#',209,'#',-41,-117,265,'#','#',283,44,'#',-10,'#',26,246,-167,-169,217,159,237,'#','#','#',72,'#',102,-110,'#','#',219,'#','#','#','#',33,239,106,'#','#',161,'#',-133,'#','#',-76,-97,-68,79,'#','#','#','#','#','#',-136,'#',22,'#','#',181,260,'#',122,-181,-98,'#','#',152,-55,116,'#','#',-197,'#',290,'#',-19,139,83,'#',67,'#','#','#','#','#',235,'#',170,'#','#','#','#','#',36,'#',130,-187,-157,-50,'#','#','#',-85,43,264,56,23,-22,78,137,'#','#','#','#','#',-58,'#','#','#',147,-174,'#',82,'#','#',-103,'#','#',204,'#',-188,'#',61,'#','#',-164,202,'#',125,-125,229,'#','#','#',-159,'#','#',193,-31,-130,'#','#','#','#','#','#',252,'#','#','#','#',138,25,-57,299,'#','#','#','#','#',136,'#','#','#','#','#','#','#','#','#','#','#','#','#','#','#',-146,'#',247,'#','#','#',203,'#','#',215,-92,115,-109,'#','#',250,-34,'#','#','#',151,'#','#','#','#','#','#','#',104,272,258,'#',266,182,-43,66,48,'#','#',-122,'#',205,68,'#',275,'#',-165,'#','#','#','#',-6,160,'#','#','#',80,'#',29,278,'#','#','#','#','#',185,'#','#','#','#','#','#','#',-70,-89,'#','#','#','#','#',60,'#','#','#','#','#',99,101,16,'#',-44,'#',-108,-67,'#','#',-15,'#','#','#','#','#',53,'#','#','#',75,-190,86,4,73,19,'#',63,50,245,220,'#',-184,'#','#',113,'#','#','#',206,42,'#','#','#',-26,-87,'#','#',-86,'#',-105,222,199,-145,268,'#','#','#','#','#','#','#',162,184,'#',155,'#','#','#','#','#','#','#',114,'#','#','#','#','#','#','#','#',92,'#','#',9,271,'#','#','#',218,'#','#','#','#',-25,-47,190,'#','#','#',-148,'#','#','#','#','#','#','#','#',27,'#','#','#',179,-166,'#','#',-75,'#','#',242,'#','#','#','#','#','#',-144,230,111,'#',-27,'#',225,149,'#',262,'#','#',117,200,234,'#','#',-124,'#','#','#','#','#',213,'#','#','#',281,'#',188,-72,'#','#','#','#','#','#','#','#','#','#','#','#','#','#','#','#','#','#','#','#','#','#','#','#','#','#','#',58,297,'#','#','#','#','#','#','#','#','#','#','#','#',285,'#','#',207,'#',-39,292,-171,-52,'#','#','#','#','#','#',-71,-114,-176], TreeLinkNode),
].forEach(function (input) {
f(input);
console.log(input);
});
}
if (DEBUG) test(connect);