深度优先遍历

发布于 / 技术 / 4 条评论

群里看到的,似乎是腾讯的一道面试题。

思路:下意识想到了递归,那么该如何递归呢?可以想象该树有很多的子树,子树可能直接是叶子结点也有可能还有子树,那么条件应当是检测到还有子树时进行递归,层层分析直到只有叶子结点代表该路走到了最深处。而输出的格式可以看出我们需要保存一条路经过的节点信息,且最后的value应当不予保存直接访问。那路径我们使用一个数组path当做栈,每经过一个则进行一个push操作将该节点入栈形成路径信息。若访问到了叶子结点则输出路径与最后的value,并返回到上一个节点,此时对path进行pop操作象征着返回到父节点,周而复始则完成了深度优先遍历。

 

var data = {
    key1: 'str1',
    key2: {
        key3: 'str3',
        key4: 'str4',
        key5: {
            key6: 'str6',
            key7: {
                key8: 'str8'
            }
        }
    },
    key9: 'str9'
    //...
}


function treeTraversal(data) {
    let path = new Array();

    function func(data) {
        for (let node in data) {
            path.push(node);
            if (typeof (data[node]) === 'object') {
                func(data[node])
            } else {
                console.log(path.join(' '), data[node]);
            }
            path.pop();
        }
    }
    func(data)
}
treeTraversal(data);
  1. avatar

    代码的css可以美化一下哈!

    1. avatar
      @tao Terry 已更新!
  2. avatar

    博主加油

  3. avatar

    写的很好,很喜欢