算法题目
给定一个不确定的 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节点
}