如何编写此递归函数以查找对象的最大深度？

Question

我正在尝试编写一个函数,它将遍历我的对象并返回对象的级别深度.

例如,如果我在此对象上运行该函数:

var test = {
  name: 'item 1',
  children: [{
    name: 'level 1 item',
    children: [{
      name: 'level 2 item'
    },
    {
      name: 'second level 2 item',
      children: [{
        name: 'level 3 item'
      }]
    }]
  }]
}

var depth = myFunction(test); // Would return 2 (0 index based) as the collection goes 3 levels deep

我一直在尝试编写一个确定最大深度的递归函数,但到目前为止我无法做到正确.这是我到目前为止:https://jsfiddle.net/6cc6kdaw/2/

似乎返回的值是每个节点命中的计数,而不是唯一级别.我明白我哪里出错了(从某种意义上说我没有过滤掉它)但是我已经盯着代码这么久以至于没有任何意义了!

有谁能够指出我哪里出错了？谢谢

Answer 1

美女

深度函数是递归表达得如此精美的函数之一 - 这个答案与Nina类似,但说明了不同的推理.

const depth = ({ children = [] }) =>
  children.length === 0
    ? 0                                      // base
    : 1 + Math.max (...children.map (depth)) // inductive

首先,我们对传入节点进行解构,children = []在未设置属性时进行分配.这允许我们使用传统的基数和集成的归纳案例来解决问题:

• 基本情况:数组为空
• 归纳案例:数组不为空,因此我们至少要处理一个元素

尼娜的回答非常巧妙地完全避免了任何if或三元?:!她通过将基础案例作为第一个参数偷偷摸摸来做到这一点Math.max!她很聪明<3

这是一个有效的例子

const depth = ({ children = [] }) =>
  children.length === 0
    ? 0
    : 1 + Math.max (...children.map (depth))

const test = 
  { name: 'level 0 item'
  , children: 
      [ { name: 'level 1 item'
        , children:
            [ { name: 'level 2 item' }
            , { name: 'second level 2 item'
              , children:
                  [ { name: 'level 3 item' } ]
              }
            ]
        }
      , { name: 'second level 1 item'
        , children:
            [ { name: 'level 2 item' }
            , { name: 'second level 2 item'
              , children: 
                  [ { name: 'level 3 item'
                    , children:
                        [ { name: 'level 4 item' } ]
                    }
                  ]
              }
            ]
        }
      ]
  }

console.log (depth (test))
// 4

野兽

我们使用了上面的一些高级函数和语言实用程序.如果我们对这个概念不熟悉,那么在第一次学习在较低层次思考之前,我们就无法达到更高层次的思考

• Math.max接受任意数量的参数.这是如何工作的？
• 我们使用rest参数语法...children将值数组转换为函数调用中的单个参数.这种转换如何正常工作？
• 我们使用map从将Array.prototype子节点数组转换为节点深度数组.这是如何运作的？我们真的需要制作一个新阵列吗？

为了培养对这些内置功能和特性的理解,我们将研究如何自己实现这些结果.我们会再次访问,depth但这次我们将用自己的努力取代所有的魔力

const depth = ({ children = [] }) =>
  children.length === 0
    ? 0                        // base
    : 1 + magicWand (children) // inductive

现在我们只需要一根魔杖......首先,我们从一些基本的手工材料开始

const isEmpty = (xs = []) =>
  xs.length === 0

const first = (xs = []) =>
  xs [0]

const rest = (xs = []) =>
  xs.slice (1)

我想继续考虑基础和归纳案例,这些原始函数与这种推理方式相辅相成.

让我们首先了解magicWand将如何(必须)发挥作用

// magicWand takes a list of nodes and must return a number
1 + magicWand (children)

那么让我们来看看我们的两个案例

• 基本情况:输入列表isEmpty,所以返回0 - 没有子节点,因此没有要添加的深度
• 归纳案例:列表中至少有一个孩子 - 计算项目的深度,在first魔法棒上挥动rest,然后取出max这两个值

我们的魔杖是完整的

const magicWand = (list = []) =>
  isEmpty (list)
    // base
    ? 0
    // inductive
    : max ( depth (first (list))
          , magicWand (rest (list))
          )

剩下的就是定义 max

const max = (x = 0, y = 0) =>
  x > y
    ? x
    : y

只是为了确保一切都在这一点上仍在工作......

const max = (x = 0, y = 0) =>
  x > y
    ? x
    : y

const isEmpty = (xs = []) =>
  xs.length === 0

const first = (xs = []) =>
  xs [0]

const rest = (xs = []) =>
  xs.slice (1)

const depth = ({ children = [] }) =>
  children.length === 0
    ? 0                        // base
    : 1 + magicWand (children) // inductive
    
const magicWand = (list = []) =>
  isEmpty (list)
    // base
    ? 0
    // inductive
    : max ( depth (first (list))
          , magicWand (rest (list))
          )

const test = 
  { name: 'level 0 item'
  , children: 
      [ { name: 'level 1 item'
        , children:
            [ { name: 'level 2 item' }
            , { name: 'second level 2 item'
              , children:
                  [ { name: 'level 3 item' } ]
              }
            ]
        }
      , { name: 'second level 1 item'
        , children:
            [ { name: 'level 2 item' }
            , { name: 'second level 2 item'
              , children: 
                  [ { name: 'level 3 item'
                    , children:
                        [ { name: 'level 4 item' } ]
                    }
                  ]
              }
            ]
        }
      ]
  }

console.log (depth (test)) // 4

因此,为了实现更高层次的思考,您必须首先想象运行程序时会发生什么

const someList =
  [ x, y, z ]

magicWand (someList)
// ???

它什么并不重要x,y并且z是.您只需要想象magicWand将使用每个独立部分构建的函数调用堆栈.随着更多项目添加到输入列表中,我们可以看到这将如何扩展...

max ( depth (x)
    , max ( depth (y)
          , max ( depth (z)
                , 0
                )
          )
    )

当我们看到我们的函数构建的计算时,我们开始看到它们的结构有相似之处.当一个模式出现时,我们可以在一个可重用的函数中捕获它的本质

在上面的计算中,max并且magicWand硬编码到我们的程序中.如果我想用树计算不同的值,我需要一个完全不同的魔杖.

此函数称为折叠,因为它f在可遍历数据结构中的每个元素之间折叠用户提供的函数.你会看到我们的签名基础和归纳案例

const fold = (f, base, list) =>
  isEmpty (list)
    ? base
    : f ( fold ( f
               , base
               , rest (list)
               )
        , first (list)
        )

现在我们可以magicWand使用我们的泛型重写fold

const magicWand = (list = []) =>
  fold ( (acc, x) => max (acc, depth (x))
       , 0
       , list
       )

该magicWand抽象不再是必要的.fold可以直接在我们的原始功能中使用.

const depth = ({ children = [] }) =>
  children.length === 0
    ? 0
    : 1 + fold ( (acc, x) => max (acc, depth (x))
               , 0
               , children
               )

当然,阅读原文要困难得多.语法糖为您提供代码中的各种快捷方式.缺点是初学者经常觉得必须总是有某种甜蜜的"速记"解决方案来解决他们的问题 - 然后当它不存在时它们会被卡住.

功能代码示例

const depth = ({ children = [] }) =>
  isEmpty (children)
    ? 0
    : 1 + fold ( (acc, x) => max (acc, depth (x))
               , 0
               , children
               )

const fold = (f, base, list) =>
  isEmpty (list)
    ? base
    : f ( fold ( f
               , base
               , rest (list)
               )
        , first (list)
        )
        
const max = (x = 0, y = 0) =>
  x > y
    ? x
    : y

const isEmpty = (xs = []) =>
  xs.length === 0
  
const first = (xs = []) =>
  xs [0]
  
const rest = (xs = []) =>
  xs.slice (1)

const test = 
  { name: 'level 0 item'
  , children: 
      [ { name: 'level 1 item'
        , children:
            [ { name: 'level 2 item' }
            , { name: 'second level 2 item'
              , children:
                  [ { name: 'level 3 item' } ]
              }
            ]
        }
      , { name: 'second level 1 item'
        , children:
            [ { name: 'level 2 item' }
            , { name: 'second level 2 item'
              , children: 
                  [ { name: 'level 3 item'
                    , children:
                        [ { name: 'level 4 item' } ]
                    }
                  ]
              }
            ]
        }
      ]
  }

console.log (depth (test))
// 4

野兽模式

潜伏在最后一个实现中depth我们看到了这个lambda(匿名函数)表达式.

(acc, x) => max (acc, depth (x))

我们即将见证我们自己制造的令人难以置信的发明.这个小lambda是如此有用,我们实际上会给它一个名字,但在我们能够利用它的真正力量之前,我们必须首先制作max和depth参数 - 我们制作了一个新的魔杖

const magicWand2 = (f, g) =>
  (acc, x) => g (acc, f (x))

const depth = ({ children = [] }) =>
  isEmpty (children)
    ? 0
    : 1 + fold (magicWand2 (depth, max), 0, children)

// Tada!

乍一看,你认为这一定是最无用的魔杖!你可能会怀疑我是那些在一切都没有点之前就不会停下来的僵尸之一.你吸入并暂停你的反应片刻

const concat = (xs, ys) =>
  xs.concat (ys)

const map = (f, list) =>
  fold (magicWand2 (f, concat), [], list)

map (x => x * x, [ 1, 2, 3, 4 ])
// => [ 16, 9, 4, 1 ]

不可否认,我们认为这很酷.但我们不会被一个双把戏小马弄得眼花缭乱.你可以明智地防止任何旧功能登陆你的程序或库,但是忽略这个功能你会很傻.

const filter = (f, list) =>
  fold ( magicWand2 (x => f (x) ? [ x ] : [], concat)
       , []
       , list
       )

filter (x => x > 2, [ 1, 2, 3, 4 ])
// [ 4, 3 ]

好吧,除了map并且filter正在以"反向"顺序组装结果的事实之外,这个魔杖还有一些严重的热量.我们之所以称它mapReduce是因为它为我们提供了两个参数,每个参数都是一个函数,并创建了一个新的缩减函数来插入fold

const mapReduce => (m, r) =>
  (acc, x) => r (acc, m (x))

1. m,映射函数 - 这使您有机会在传递元素之前转换...
2. r,reduce函数 - 该函数将累加器与映射元素的结果相结合

至于fold将结果组装成"反向",则不然.这恰好是一个正确的折叠.下面,我们可以想象f一些二进制函数(即+) - 看前缀表示法中的计算f (x y),中缀表示法x + y应该有助于突出关键区别

foldR (f, base, [ x, y, z ])
// = f (f (f (base, z), y), x)
// = ((base + z) + y) + x

foldL (f, base, [ x, y, z ])
// = f (f (f (base, x), y), z)
// = (((base + x) + y) + z

所以,让我们来定义左倍,foldL现在-我改名fold来foldR,放在这里,所以我们可以并排看到它们的一面.

const foldL = (f, base, list) =>
  isEmpty (list)
    ? base
    : foldL ( f
            , f (base, first (list))
            , rest (list)
            )

const foldR = (f, base, list) =>
  isEmpty (list)
    ? base
    : f ( foldR ( f
               , base
               , rest (list)
               )
        , first (list)
        )

很多JavaScript开发人员都不知道reduceRight存在Array.prototype.如果您只使用过交换功能reduce,则无法检测到差异.

好了,来解决我们的map和filter,我们只是要取代我们fold用结合foldL

const map = (f, list) =>
  foldL (mapReduce (f, concat), [], list)

const filter = (f, list) =>
  foldL (mapReduce (x => f (x) ? [ x ] : [], concat), [], list)

const square = x =>
  x * x

const gt = x => y =>
  y > x

map (square, filter (gt (2), [ 1, 2, 3, 4 ]))
// => [ 9, 16 ]

有了我们自己的map,我们可以重写depth一点我们原来的形式......

const depth = ({ children = [] }) =>
  isEmpty (children)
    ? 0
    : 1 + foldL ( max
                , 0
                , map (depth, children)
                )

但我希望我们停在那里思考为什么这比直接depth使用更糟糕mapReduce...

适可而止

让我们花点时间思考一下我们在那里做了什么map- filter例子.filter遍历整个输入数组,调用gt (2)每个数字,产生一个中间结果[ 3, 4 ].然后 在中间结果中map调用 squarenumber,产生最终值[ 9, 16 ].数据变得很大,我们不希望看到这样的代码:

myBigData.map(f).map(g).filter(h).map(i).map(j).reduce(k, base)

mapReduce是有一种会破坏其旁观者的权力.你觉得我心甘情愿地写这个answerette,但我只是一个囚犯mapReduce!这种结构是一些社区称之为换能器的核心 - 这恰好是我在这里所写的关于SO的主题.我们开发了折叠直觉的折叠 - 和魔术一样,耗尽多个循环被折叠成一个折叠.如果您对这个主题感兴趣,我建议您进一步阅读!

Answer 2

您可以映射每个孩子的深度并获取其最大值.

function getDepth(object) {
    return 1 + Math.max(0, ...(object.children || []).map(getDepth));
}

var test = { name: 'item 1', children: [{ name: 'level 1 item', children: [{ name: 'level 2 item' }, { name: 'second level 2 item', children: [{ name: 'level 3 item' }] }] }] },
    depth = getDepth(test) - 1; // zero based

console.log(depth);

Answer 3

这是一个建议：

function depth(o){
  var values;
  if (Array.isArray(o)) values = o;
  else if (typeof o === "object") values = Object.keys(o).map(k=>o[k]);
  return values ? Math.max.apply(0, values.map(depth))+1 : 1;
}

function depth(o){
  var values;
  if (Array.isArray(o)) values = o;
  else if (typeof o === "object") values = Object.keys(o).map(k=>o[k]);
  return values ? Math.max.apply(0, values.map(depth))+1 : 1;
}

编辑：这是一个通用的解决方案。我仍然不确定您是否想要一个非常具体的（即带有一个children字段或一个通用字段）。

Answer 4

我对您的代码进行了一些更改，以按照您的要求工作：

function getDepth(node, depth = 0) {
    if (!!node.children && node.children.length > 0) {
        var childDepths = [];
        depth++;

        for (var i = 0; i < node.children.length; i++) {
            childDepths.push(getDepth(node.children[i]));
        }
        return depth + Math.max(...childDepths);
    }

    return depth;
}

var depth = getDepth(root);

console.log('currentMaxDepth', depth);
console.log('root', root);

诀窍是测量同一水平上兄弟姐妹的深度，然后选择其中最深的。这也是一个jsfiddle：https ://jsfiddle.net/2xk7zn00/