天天看點

lintcode二叉樹的鋸齒形層次周遊 (雙端隊列)

  給出一棵二叉樹,傳回其節點值的鋸齒形層次周遊(先從左往右,下一層再從右往左,層與層之間交替進行) 

  給出一棵二叉樹 <code>{3,9,20,#,#,15,7}</code>,

  傳回其鋸齒形的層次周遊為:

  我們用雙端隊列模拟一下這個過程:開始的時候是正向周遊,3通過push_front()放入隊列Q, 形成Q[3]。接着我們規定正向周遊的時候從隊列前端去元素,下一層元素放入隊列的時候是放入隊列的後端;而反向周遊的時候正好相反,唯一不同的就是反向周遊時,下一層的右孩子結點(如果有)先放入隊列的前端。

  開始Q[3](從前端取數字), 然後下一層放入後是Q[9,20](從後端去數字),20的下一層放入後是Q[15,7,9], 然後變成Q[15,7](從前端去數字),最後得到周遊的結果。