一. 審題

面試題：

給定一個 RootView，打印其內 View Tree 的每個 View。

在 Android 下，UI 的佈局結構，對標到數據結構中，本質就是一個由 View 和 ViewGroup 組成的多叉樹結構。其中 View 只能作為葉子節點，而 ViewGroup 是可以存在子節點的。

上圖就是一個典型的 ViewTree 的結構，而想要遍歷這個 ViewTree，還需要用到兩個 ViewGroup 的方法。

• getChildCount()：獲取其子 View 的個數。
• getChildAt(int)：獲取對應索引的子 View。

對於 View，無需過多處理，直接打印輸出即可。而 ViewGroup，除了打印自身的這個節點之外，還需要打印其子節點。

二. 解題的三種實現

2.1 遞歸實現

當一個大問題，可以被拆分成多個小問題，並且分解後的小問題，和大問題相比，只是數據規模不同，求解思路完全一致的問題，非常適合遞歸來實現。

fun recursionPrint(root: View) {
 printView(root)
 if (root is ViewGroup) {
 for (childIndex in 0 until root.childCount) {
 val childView = root.getChildAt(childIndex)
 recursionPrint(childView)
 }
 }
}

遞歸確實可以很清晰的實現功能，但是它有一個致命的問題，當遞歸深度過深的時候，會爆棧。反應在異常上，就是會拋出 StackOverflowError 這個異常。

面試的時候，面試者解決問題的思路，使用了遞歸思想，通常都會很自然的問問 JVM 的棧幀，以及為什麼會出現 StackOverflowError 異常。

當然這不是本文的重點，大家瞭解一下即可。

簡單來說，每啟動一個現場，JVM 都會為其分配一個 Java 棧，每調用一個方法，都會被封裝成一個棧幀，進行壓棧操作，當方法執行完成之後，又會執行彈棧操作。而每個棧幀中，當前調用的方法的一些局部變量、動態連接，以及返回地址等數據。

Java 棧和數據結構的棧結構一樣，有兩個操作，壓棧（入棧）、彈棧（出棧），是一個先入後出（FILO）的結構。這一塊的東西，延伸出來就比較多了，你可以簡單的理解為調用方法就會壓棧，方法執行完會彈棧。

每次方法的調用，執行壓棧的操作，但是每個棧幀，都是要消耗內存的。一旦超過了限制，就會爆掉，拋出 StackOverflowError。

遞歸確實簡單，但是問題不少。面試官也不怕面試者寫遞歸代碼，後續可以有一連串問題等著。

2.2 廣度優先實現

前面也提到，這道題本質上就是數據結構中，樹的遍歷。那最先想到的就是深度優先和廣度優先兩種遍歷策略。

我們先來看看廣度優先的實現，廣度優先的過程，就是對每一層節點依次訪問，訪問完了再進入下一層。就是按樹的深度，一層層的遍歷訪問。

ABCDEFGHI 就是上圖這個多叉樹，使用廣度優先算法的遍歷結果。

廣度優先非常適合用先入先出的隊列來實現，每次子 View 都入隊尾，而從對頭取新的 View 進行處理。

代碼如下：

fun breadthFirst(root :View){
 val viewDeque = LinkedList<View>()
 var view = root
 viewDeque.push(view)
 while (!viewDeque.isEmpty()){
 view = viewDeque.poll()
 printView(view)
 if(view is ViewGroup){
 for(childIndex in 0 until view.childCount){
 val childView = view.getChildAt(childIndex)
 viewDeque.addLast(childView)
 }
 }
 }
}

這裡直接利用 LinkedList 來實現隊列，它本身就實現了雙端隊列 Deque 接口。

2.3 深度優先實現

說完廣度深度，再繼續看看深度優先。

深度優先的過程，就是對每個可能的分支路徑，深度到葉子節點，並且每個節點只訪問一次。

ADIHCBGFE 就是上圖這個多叉樹，使用深度優先算法的遍歷結果。

在實現上，深度優先非常適合用先入後出的棧來實現。邏輯不復雜，直接上執行時，棧的數據變換。

代碼實現如下：

fun depthFirst(root :View){
 val viewDeque = LinkedList<View>()
 var view = root
 viewDeque.push(view)
 while (!viewDeque.isEmpty()){
 view = viewDeque.pop()
 printView(view)
 if(view is ViewGroup){
 for(childIndex in 0 until view.childCount){
 val childView = view.getChildAt(childIndex)
 viewDeque.push(childView)
 }
 }
 }
}

依然利用 LinkedList 來當棧使用，利用 push() 和 pop() 實現棧的邏輯。

三. 小結時刻

今天聊的 View 樹的遍歷，本質上就是數據結構中多叉樹的遍歷，不同的實現方式用來解決不同的問題。

起始這道題，還有一些變種，例如統計 ViewGroup 子 View 的數量、分層打印 ViewTree、查找 ID 為 Xxx 的 View 等，有興趣可以試著寫寫代碼。

算法題就是這樣，有一些是考驗編碼能力，另一些是解決問題的思路，多思考多寫，才是正道。

今天就到這裡，有問題可以在評論區留言，如果覺得不錯，歡迎轉發、點贊，謝謝！

在頭條號私信我。我會送你一些我整理的學習資料，包含：Android反編譯、算法、設計模式、虛擬機、Linux、Kotlin、Python、爬蟲、Web項目源碼。