关于js二叉树遍历的问题？

Question

class TreeNode {
    constructor(val) {
        this.val = val;
        this.left = this.right = null;
    }
}

function init(){
    var root = new TreeNode(5)
    var node1 = new TreeNode(4)
    var node2 = new TreeNode(8)
    var node3 = new TreeNode(11)
    var node4 = new TreeNode(13)
    var node5 = new TreeNode(4)
    var node6 = new TreeNode(7)
    var node7 = new TreeNode(2)
    var node8 = new TreeNode(1)
    root.left = node1
    root.right = node2
    node1.left = node3
    node2.left = node4
    node2.right = node5
    node3.left = node6
    node3.right = node7
    node5.right = node8
    return root
}
var root = init()

init后得到这样一棵二叉树

如何遍历才能得到这样的数据?????

var result = [
    [5, 4, 11, 7],
    [5, 4, 11, 2],
    [5, 8, 13],
    [5, 8, 4, 1],
]

即按照分支左右分支遍历（描述可能有问题，大概是这个意思）

Answer 1

想象一下，在任何一个节点，你手里有这个节点和一条从根下来的路径。
接下来就是选择节点的下级路径中的每一条了，如果没有下级，则路径就是当前路径了。

function findPath (root) {
  const result = []
  if (!root) return result
  const list = [{ node: root, path: [root.val] }] // 从根开始遍历。list是待处理的节点和该节点路径
  while (list.length) {
    const { node, path } = list.shift()
    !node.left && !node.right && result.push(path)
    ;[node.left, node.right].filter(c => c && list.push({ node: c, path: [...path, c.val] }))
  }
  return result
}

以上是广度优先遍历。也可以深度优先：

function getPath (root) {
    if (!root) return []
    const left = getPath(root.left), right = getPath(root.right)
    const pathList = left.concat(right).map(p => (p.unshift(root.val), p))
    return pathList.length ? pathList : [[root.val]]
}