十五:查找二叉树中所有路径
思路:
时间复杂度:O(n²)
空间复杂度:O(n²)
定义一个paths存储所有路径
定义一个递归函数next,接收三个参数(二叉树root,累加path,存储paths的集合)
如果root不存在直接返回,否则path累加当前root的节点值
如果当前节点是叶子节点,将累加后的path存储在paths中
不是叶子节点,分别递归左右子树,传入左右子树,累加path,集合
算法如下
/**
* 寻找二叉树所有路径
* @param {*} binaryTree 二叉树
*/
function findBinaryTreeAllPath(binaryTree) {
// 存储所有路径
let paths = []
/**
* 递归
* @param {*} root 二叉树
* @param {*} path 路径
* @param {*} paths 存储的路径
*/
function next(root, path, paths) {
// 如果二叉树不存在,返回
if (!root) return
path += root.value
// 叶子节点 存储路径
if (!root.left && !root.right) paths.push(path)
else {
path += '=>'
// 遍历左子树
next(root.left, path, paths)
// 遍历右子数
next(root.right, path, paths)
}
}
// 从根节点开始
next(binaryTree, '', paths)
return paths
}