import Ġjava . util .* Ċ Ċ class ĠTreeNode ( var Ġ` val `: ĠInt ) Ġ{ ĊĠĠĠ Ġvar Ġleft : ĠTreeNode ? Ġ= Ġnull ĊĠĠĠ Ġvar Ġright : ĠTreeNode ? Ġ= Ġnull Ċ } Ċ Ċ class ĠTree Utils Ġ{ ĊĠĠĠ Ġcompanion Ġobject Ġ{ ĊĠĠĠĠĠĠĠ Ġfun Ġbuild Tree ( nums : ĠArray < Int ?> ): ĠTreeNode ? Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( nums . isEmpty ()) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġnull ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġroot Ġ= ĠTreeNode ( nums [ 0 ] !! ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġqu Ġ= ĠLinkedList < TreeNode >() ĊĠĠĠĠĠĠĠĠĠĠĠ Ġqu . add ( root ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġi Ġ= Ġ 1 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġwhile Ġ( i Ġ< Ġnums . size ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( qu . isEmpty ()) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġbreak ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġnode Ġ= Ġqu . poll () !! ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġnums [ i ]?. let Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠTreeNode ( it ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ?. let Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġnode . left Ġ= Ġit ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġqu . add ( it ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġi ++ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( i Ġ< Ġnums . size ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġnums [ i ]?. let Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠTreeNode ( it ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ?. let Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġnode . right Ġ= Ġit ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġqu . add ( it ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġi ++ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġroot ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġfun Ġprint Tree ( root : ĠTreeNode ?) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( root Ġ== Ġnull ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġreturn ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġqu Ġ= ĠLinkedList < TreeNode ?> () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġqu . add ( root ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġfinished Ġ= Ġfalse ĊĠĠĠĠĠĠĠĠĠĠĠ Ġwhile Ġ(! qu . isEmpty () Ġ&& Ġ! finished ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġfinished Ġ= Ġtrue ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġlevel Num Ġ= Ġqu . size ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġfor Ġ( i Ġin Ġ 0 Ġuntil Ġlevel Num ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġnode Ġ= Ġqu . poll () ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( node Ġ!= Ġnull ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġfinished Ġ= Ġfalse ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġprint ("% d Ġ". format ( node .` val ` )) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġqu . add ( node . left ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġqu . add ( node . right ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠSystem . out . printf ("* ") ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġqu . add ( null ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġqu . add ( null ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġprintln () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġfun ĠgetNode ( ĊĠĠĠĠĠĠĠĠĠĠĠ Ġroot : ĠTreeNode ?, ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ` val `: ĠInt ĊĠĠĠĠĠĠĠ Ġ): ĠTreeNode ? Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( root Ġ== Ġnull ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġnull ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( root .` val ` Ġ== Ġ` val `) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġroot ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġleft Ġ= ĠgetNode ( root . left , Ġ` val `) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġright Ġ= ĠgetNode ( root . right , Ġ` val `) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( left Ġ!= Ġnull ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġleft ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġright ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} Ċ }