算法題目
給定一個不確定的 Json 對象，求 Json 子節點的最大深度（編程語言不限，不可寫偽代碼）。如下：
{
"item"
:{
"data"
: {
"text"
:
"123"
,
},
"children"
: [{
"data"
: {
"text"
:
"234"
},
"children"
: []
}, {
"data"
: {
"text"
:
"345"
},
"children"
: [{
"data"
: {
"text"
:
"456"
},
"children"
: []
}, {
"data"
: {
"text"
:
"plid"
},
"children"
: [{
"data"
: {
"text"
:
"567"
},
"children"
: [....]
}, {
"data"
: {
"text"
:
"678"
},
"children"
: [...]
}
]
}, {
// 不確定長度的Children節點
}
}
你知道如何解答嗎？
給你 10 分鐘時間，能否搞定？
想到答案的同學，可以在評論區回覆，也可點擊左下角“閱讀原文”，登錄 TesterHome 社區回覆帖子。
你可能想不到的最佳參考答案是？
參考答案作者為@思寒，資深測試架構師，霍格沃茲測試學院校長，開源工具 AppCrawler 作者。
解法一
其實是個遞歸算法，Json 本質是一個 tree 節奏的數據，先把 Json 轉成標準的各個語言的結構體，比如 Python 的 dict 或者 Java 的 HashMap。
剩下的就是遞歸判斷 children 的類型並計數深度。我碰巧之前寫過類似的算法，不過 Scala 的代碼。。。
不得不說這個算法其實是測試工程裡用的非常多的場景。用遞歸解決深層次數據的分析問題，在很多工具裡都有一些應用的。
AppCrawler 裡也有好幾段是關於這個算法的使用的，比如從 Xpath 匹配的節點中反向生成 Xpath 定位表達式，把 HTML 網頁的 page source 轉成 Appium 兼容的 XML 格式，對數據結構做扁平化好進行數據對比。
def
getAttributesFromNode(node:
Node
):
ListBuffer
[
Map
[
String
,
String
]] ={
val attributesList =
ListBuffer
[
Map
[
String
,
String
]]()
//遞歸獲取路徑,生成可定位的xpath表達式
def
getParent(node:
Node
):
Unit
= {
if
(node.hasAttributes) {
val attributes = node.getAttributes
var
attributeMap =
Map
[
String
,
String
]()
0
until
attributes.getLength
foreach
(i => {
val kv = attributes.item(i).asInstanceOf[Attr
]
attributeMap ++= Map
(kv.getName -> kv.getValue)
})
attributeMap ++= Map
(
"name()"
-> node.getNodeName)
attributeMap ++= Map
(
"innerText"
-> node.getTextContent.trim)
attributesList += attributeMap
}
if
(node.getParentNode !=
null
) {
getParent(node.getParentNode)
}
}
getParent(node)
//返回一個從root到leaf的屬性列表
return
attributesList.reverse
}
解法二
巧用 Shell 腳本編程來實現一個最簡單的解法，正好最近剛在霍格沃茲測試學院分享了 Linux 三劍客公開課的技術，利用 Shell 腳本來實現下面這個解法。
depth(){
echo
"$1"
\
sed
's#"1*"##g'
\
| grep -oE
'{|}'
\
| awk
'/{/{a+=1}/}/{a-=1}{if(max
"data": {
"text": "123",
},
"children": [{
"data": {
"text": "234"
},
"children": []
}, {
"data": {
"text": "345"
},
"children": [{
"data": {
"text": "456"
},
"children": []
}, {
"data": {
"text": "plid"
},
"children": [{
"data": {
"text": "567"
},
"children": [....]
}, {
"data": {
"text": "678"
},
"children": [...]
}
]
}, {
// 不確定長度的Children節點
}