package Ġcom . daily . algo th rim . leetcode Ċ Ċ import Ġjava . util .* Ċ Ċ /** Ċ Ġ* Ġ 1 1 6 . Ġ å¡« åħħ æ¯ıä¸ª èĬĤçĤ¹ çļĦ ä¸ĭ ä¸Ģä¸ª åı³ ä¾§ èĬĤçĤ¹ æĮĩéĴĪ Ċ Ġ* Ċ Ġ* Ġ ç»Ļ å®ļ ä¸Ģä¸ª å®Į ç¾İ äºĮ åıī æłĳ ï¼Į åħ¶ æīĢæľī åı ¶ åŃĲ èĬĤçĤ¹ éĥ½ åľ¨ åĲĮ ä¸Ģ å±Ĥ ï¼Į æ¯ıä¸ª çĪ¶ èĬĤçĤ¹ éĥ½ æľī ä¸¤ä¸ª åŃĲ èĬĤçĤ¹ ãĢĤ Ċ Ġ* Ġ å¡« åħħ å®ĥçļĦ æ¯ıä¸ª Ġnext Ġ æĮĩéĴĪ ï¼Į è®© è¿Ļä¸ª æĮĩéĴĪ æĮĩåĲĳ åħ¶ ä¸ĭ ä¸Ģä¸ª åı³ ä¾§ èĬĤçĤ¹ ãĢĤ å¦Ĥæŀľ æī¾ ä¸įåĪ° ä¸ĭ ä¸Ģä¸ª åı³ ä¾§ èĬĤçĤ¹ ï¼Į åĪĻ å°Ĩ Ġnext Ġ æĮĩéĴĪ è®¾ç½®ä¸º ĠNULL ãĢĤ Ċ Ġ* Ċ Ġ* Ġ åĪĿå§ĭ çĬ¶æĢģ ä¸ĭ ï¼Į æīĢæľī next Ġ æĮĩéĴĪ éĥ½ è¢« è®¾ç½®ä¸º ĠNULL ãĢĤ Ċ Ġ*/ Ċ class ĠConnect Ġ{ ĊĊĠĠĠ Ġcompanion Ġobject Ġ{ ĊĠĠĠĠĠĠĠ Ġ@ Jvm Static ĊĠĠĠĠĠĠĠ Ġfun Ġmain ( args : ĠArray < String >) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ ĠConnect (). solution ( Node ( 1 , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠNode ( 2 , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠNode ( 4 ), ĠNode ( 5 )), ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠNode ( 3 , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠNode ( 6 ), ĠNode ( 7 ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ)) ?. let Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġit . print Mid ( it ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġprintln () ĊĠĠĠĠĠĠĠĠĠĠĠ ĠConnect (). solution V 2 ( Node ( 1 , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠNode ( 2 , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠNode ( 4 ), ĠNode ( 5 )), ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠNode ( 3 , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠNode ( 6 ), ĠNode ( 7 ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ)) ?. let Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġit . print Mid ( it ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġdata Ġclass ĠNode ( var Ġdata : ĠInt , Ġvar Ġleft : ĠNode ? Ġ= Ġnull , Ġvar Ġright : ĠNode ? Ġ= Ġnull , Ġvar Ġnext : ĠNode ? Ġ= Ġnull ) Ġ{ ĊĠĠĠĠĠĠĠ Ġfun Ġprint Mid ( node : ĠNode ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġnode . left ?. let Ġ{ Ġprint Mid ( it ) Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġprintln ( node . data ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġprintln (" next : Ġ Ġ${ node . next ?. data }") ĊĠĠĠĠĠĠĠĠĠĠĠ Ġnode . right ?. let Ġ{ Ġprint Mid ( it ) Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* Ġ å±Ĥ æ¬¡ éģįåİĨ ĊĠĠĠĠ Ġ* ĠO ( n ) ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġfun Ġsolution ( root : ĠNode ?): ĠNode ? Ġ{ ĊĠĠĠĠĠĠĠ Ġif Ġ( root Ġ== Ġnull ) Ġreturn Ġroot ĊĠĠĠĠĠĠĠ Ġval Ġdeque Ġ= ĠArray Deque < Node >() ĊĠĠĠĠĠĠĠ Ġval Ġflag Ġ= ĠNode ( 1 ) ĊĠĠĠĠĠĠĠ Ġdeque . offer ( root ) ĊĠĠĠĠĠĠĠ Ġdeque . offer ( flag ) ĊĠĠĠĠĠĠĠ Ġwhile Ġ( deque . isNotEmpty ()) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġpre : ĠNode ? Ġ= Ġnull ĊĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġitem Ġ= Ġdeque . poll () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġwhile Ġ( item Ġ!= Ġflag Ġ&& Ġitem Ġ!= Ġnull ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġitem . left ?. let Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġdeque . offer ( it ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġitem . right ?. let Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġdeque . offer ( it ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġpre ?. next Ġ= Ġitem ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġpre Ġ= Ġitem ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġitem Ġ= Ġdeque . poll () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( deque . isNotEmpty ()) Ġdeque . offer ( flag ) ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġreturn Ġroot ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠO ( n ) ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġfun Ġsolution V 2 ( root : ĠNode ?): ĠNode ? Ġ{ ĊĠĠĠĠĠĠĠ Ġif Ġ( root Ġ== Ġnull ) Ġreturn Ġroot ĊĠĠĠĠĠĠĠ Ġvar Ġmost Left Ġ= Ġroot ĊĊĠĠĠĠĠĠĠ Ġwhile Ġ( most Left Ġ!= Ġnull ) Ġ{ ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġhead Ġ= Ġmost Left ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġwhile Ġ( head Ġ!= Ġnull ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġ 1 Ġ åĲĮ çĪ¶ äº² çĽ¸ éĤ » èĬĤçĤ¹ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġhead . left ?. next Ġ= Ġhead . right ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġ 2 Ġ ä¸įåĲĮ çĪ¶ äº² çĽ¸ éĤ » èĬĤçĤ¹ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( head . next Ġ!= Ġnull ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġhead . right ?. next Ġ= Ġhead . next ?. left ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġhead Ġ= Ġhead . next ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġmost Left Ġ= Ġmost Left . left ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġreturn Ġroot ĊĠĠĠ Ġ} Ċ }