對于一棵多叉樹,我們可以通過 “左孩子右兄弟” 表示法,將其轉(zhuǎn)化成一棵
二叉樹。
如果我們認(rèn)為每個結(jié)點的子結(jié)點是無序的,那么得到的二叉樹可能不唯一。換句話說,每個結(jié)點可以選任意子結(jié)點作為左孩子,并按任意順序連接右兄弟。
給定一棵包含 N 個結(jié)點的多叉樹,結(jié)點從 1 至 N 編號,其中 1 號結(jié)點是根,每個結(jié)點的父結(jié)點的編號比自己的編號小。請你計算其通過 “左孩子右兄弟” 表示法轉(zhuǎn)化成的二叉樹,高度最高是多少。注:只有根結(jié)點這一個結(jié)點的樹高度為 0 。
例如如下的多叉樹:
可能有以下 3 種 (這里只列出 3 種,并不是全部) 不同的 “左孩子右兄弟”
表示:
其中最后一種高度最高,為 4。