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],
]
即按照分支左右分支遍历(描述可能有问题,大概是这个意思)
###想象一下,在任何一个节点,你手里有这个节点和一条从根下来的路径。
接下来就是选择节点的下级路径中的每一条了,如果没有下级,则路径就是当前路径了。
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]]
}
###前序遍历+叶子节点判断