本文首发 TesterHome 社区，原文链接 https://testerhome.com/topics/17949

算法题目

给定一个不确定的 Json 对象，求 Json 子节点的最大深度（编程语言不限，不可写伪代码）。如下：

      1. {

  2.    "item":{

  3.           "data": {

  4.             "text": "123",

  5.         },

  6.         "children": [{

  7.             "data": {

  8.                 "text": "234"

  9.             },

  10.             "children": []

  11.         }, {

  12.             "data": {

  13.                 "text": "345"

  14.             },

  15.             "children": [{

  16.                 "data": {

  17.                     "text": "456"

  18.                 },

  19.                 "children": []

  20.             }, {

  21.                 "data": {

  22.                     "text": "plid"

  23.                 },

  24.                 "children": [{

  25.                     "data": {

  26.                         "text": "567"

  27.                     },

  28.                     "children": [....]

  29.                 }, {

  30.                     "data": {

  31.                         "text": "678"

  32.                     },

  33.                     "children": [...]

  34.                 }

  35.                 ]

  36.         }, {

  37.                 // 不确定长度的Children节点

  38.             }

  39. }

你知道如何解答吗？

给你 10 分钟时间，能否搞定？

想到答案的同学，可以在评论区回复，也可点击左下角“阅读原文”，登录 TesterHome 社区回复帖子。

你可能想不到的最佳参考答案是？

参考答案作者为@思寒，资深测试架构师，霍格沃兹测试学院校长，开源工具 AppCrawler 作者。

解法一

其实是个递归算法，Json 本质是一个 tree 节奏的数据，先把 Json 转成标准的各个语言的结构体，比如 Python 的 dict 或者 Java
的 HashMap。

剩下的就是递归判断 children 的类型并计数深度。我碰巧之前写过类似的算法，不过 Scala 的代码。。。

不得不说这个算法其实是测试工程里用的非常多的场景。用递归解决深层次数据的分析问题，在很多工具里都有一些应用的。

AppCrawler 里也有好几段是关于这个算法的使用的，比如从 Xpath 匹配的节点中反向生成 Xpath 定位表达式，把 HTML 网页的 page
source 转成 Appium 兼容的 XML 格式，对数据结构做扁平化好进行数据对比。

      1. def getAttributesFromNode(node: Node): ListBuffer[Map[String, String]] ={

  2.   val attributesList = ListBuffer[Map[String, String]]()

  3.   //递归获取路径,生成可定位的xpath表达式

  4.   def getParent(node: Node): Unit = {

  5.     if (node.hasAttributes) {

  6.       val attributes = node.getAttributes

  7.       var attributeMap = Map[String, String]()

  8.   


  9.       0 until attributes.getLength foreach (i => {

  10.         val kv = attributes.item(i).asInstanceOf[Attr]

  11.         attributeMap ++= Map(kv.getName -> kv.getValue)

  12.       })

  13.       attributeMap ++= Map("name()" -> node.getNodeName)

  14.       attributeMap ++= Map("innerText" -> node.getTextContent.trim)

  15.       attributesList += attributeMap

  16.     }

  17.   


  18.     if (node.getParentNode != null) {

  19.       getParent(node.getParentNode)

  20.     }

  21.   }

  22.   getParent(node)

  23.   //返回一个从root到leaf的属性列表

  24.   return attributesList.reverse

  25.   


  26. }

解法二

巧用 Shell 脚本编程来实现一个最简单的解法 ，正好最近刚在霍格沃兹测试学院分享了 Linux 三剑客公开课的技术，利用 Shell
脚本来实现下面这个解法。

      1. depth(){

  2. echo "$1" \

  3. sed 's#"[^"]*"##g'  \

  4. |  grep -oE  '{|}' \

  5. | awk '/{/{a+=1}/}/{a-=1}{if(max<a) max=a}{print max,a}END{print "max depth="max}'

  6. }

  7.   


  8. # 结果貌似是6

  9. depth  '

  10. {

  11.    "item":{

  12.           "data": {

  13.             "text": "123",

  14.         },

  15.         "children": [{

  16.             "data": {

  17.                 "text": "234"

  18.             },

  19.             "children": []

  20.         }, {

  21.             "data": {

  22.                 "text": "345"

  23.             },

  24.             "children": [{

  25.                 "data": {

  26.                     "text": "456"

  27.                 },

  28.                 "children": []

  29.             }, {

  30.                 "data": {

  31.                     "text": "plid"

  32.                 },

  33.                 "children": [{

  34.                     "data": {

  35.                         "text": "567"

  36.                     },

  37.                     "children": [....]

  38.                 }, {

  39.                     "data": {

  40.                         "text": "678"

  41.                     },

  42.                     "children": [...]

  43.                 }

  44.                 ]

  45.         }, {

  46.                 // 不确定长度的Children节点

  47.             }

  48. }

  49. '  

  50.   


  51. # testerhome的json接口，貌似是4

  52. depth "$(curl https://testerhome.com/api/v3/topics.json 2>/dev/null)" 

  53. # taobao的某个接口，结果为2

  54. depth "$(curl http://ip.taobao.com/service/getIpInfo.php?ip=63.223.108.42 2>/dev/null )"

**

来霍格沃兹测试开发学社，学习更多软件测试与测试开发的进阶技术，知识点涵盖web自动化测试 app自动化测试、接口自动化测试、测试框架、性能测试、安全测试、持续集成/持续交付/DevOps，测试左移、测试右移、精准测试、测试平台开发、测试管理等内容，课程技术涵盖bash、pytest、junit、selenium、appium、postman、requests、httprunner、jmeter、jenkins、docker、k8s、elk、sonarqube、jacoco、jvm-sandbox等相关技术，全面提升测试开发工程师的技术实力
QQ交流群：484590337
公众号 TestingStudio
点击获取更多信息