Android 字節跳動演算法題：給定ViewGroup列印其內所有的View

2019 年 10 月 7 日
筆記

一. 審題

面試題：

給定一個 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 等，有興趣可以試著寫寫程式碼。

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