package Ġcom . leetcode . binary tree Ċ Ċ import Ġjava . util .* Ċ import Ġkotlin . collections . ArrayList Ċ Ċ /** Ċ Ġ* ĠCreated Ġby Ġli uq ing . yang Ċ Ġ* Ġ 2 0 2 0 / 4 / 1 9 . Ċ Ġ* ĠEmail : Ġ 1 2 3 9 6 0 4 8 5 9 @ qq . com Ċ Ġ*/ Ċ Ċ class ĠC essor Node Ġ{ ĊĠĠĠ Ġfun Ġpre decessor ( node : ĠTreeNode ): ĠTreeNode ? Ġ{ ĊĠĠĠĠĠĠĠ Ġ// Ġstep Ġ 1 ĊĠĠĠĠĠĠĠ Ġvar Ġcur : ĠTreeNode ? Ġ= Ġnode . left ĊĠĠĠĠĠĠĠ Ġif Ġ( cur Ġ!= Ġnull ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġwhile Ġ( cur Ġ!= Ġnull ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġcur Ġ= Ġcur . right ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġcur ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ// Ġstep Ġ 2 ĊĠĠĠĠĠĠĠ Ġvar Ġpre : ĠTreeNode ? Ġ= Ġnode ĊĠĠĠĠĠĠĠ Ġwhile Ġ( pre ?. parent Ġ!= Ġnull Ġ&& Ġpre Ġ== Ġpre . parent ?. left ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġpre Ġ= Ġnode . parent ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġreturn Ġpre ?. parent ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġfun Ġpre order ( root : ĠTreeNode ) Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġstack Ġ= ĠStack < TreeNode >() ĊĠĠĠĠĠĠĠ Ġstack . push ( root ) ĊĠĠĠĠĠĠĠ Ġwhile Ġ( stack . isNotEmpty ()) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġcurr Ġ= Ġstack . pop () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġprintln ( curr ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġcurr ?. right ?. let Ġ{ Ġstack . push ( it ) Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġcurr ?. left ?. let Ġ{ Ġstack . push ( it ) Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġfun Ġin order ( root : ĠTreeNode ) Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġstack Ġ= ĠStack < TreeNode >() ĊĠĠĠĠĠĠĠ Ġvar Ġcurr : ĠTreeNode ? Ġ= Ġroot ĊĠĠĠĠĠĠĠ Ġwhile Ġ( curr Ġ!= Ġnull Ġ|| Ġstack . isNotEmpty ()) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġcurr Ġ= Ġif Ġ( curr Ġ!= Ġnull ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġstack . push ( curr ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġcurr . left ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġtmp Ġ= Ġstack . pop () ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġprintln ( tmp ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġtmp . right ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġfun Ġpost order ( root : ĠTreeNode ) Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġstack Ġ= ĠStack < TreeNode >() ĊĠĠĠĠĠĠĠ Ġval Ġret Ġ= ĠStack < TreeNode >() ĊĠĠĠĠĠĠĠ Ġvar Ġcurr : ĠTreeNode ? Ġ= Ġroot ĊĊĠĠĠĠĠĠĠ Ġstack . push ( curr ) ĊĠĠĠĠĠĠĠ Ġwhile Ġ( stack . isNotEmpty ()) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġcurr Ġ= Ġstack . pop () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġret . push ( curr ) ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġcurr ?. left ?. let Ġ{ Ġstack . push ( it ) Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġcurr ?. right ?. let Ġ{ Ġstack . push ( it ) Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġwhile Ġ( ret . isNotEmpty ()) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġprintln ( ret . pop ()) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġfun Ġlevel Order ( root : ĠTreeNode ) Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġqueue Ġ= ĠLinkedList < TreeNode >() ĊĠĠĠĠĠĠĠ Ġqueue . offer ( root ) ĊĠĠĠĠĠĠĠ Ġwhile Ġ( queue . isNotEmpty ()) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġhead Ġ= Ġqueue . poll () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġhead ?. left ?. let Ġ{ Ġqueue . offer ( it ) Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġhead ?. right ?. let Ġ{ Ġqueue . offer ( it ) Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} Ċ } Ċ