二叉树中和为某一值的路径(一)
题目描述
示例
代码
代码1 深度优先遍历（DFS），计算每条路径总和
js
/*
深度优先遍历
log(root.val)
dfs(root.left)
dfs(root.right)
采用深度优先遍历二叉树的路径节点，
同时计算二叉树路径节点的数字之和，
当到达叶子节点且路径的数字之和等于 sum 则说明二叉树中存在节点和为指定值的路径
1、特殊情况：当二叉树为空，则返回 false
2、遍历根节点的左右子树，记录根节点的数字之和 total
当节点的左右子树均为空，且 total == sum，则返回 true
3、递归 该节点的左右子树，做上述计算
*/
function hasPathSum( root , sum ) {
if(!root) return false
return preOrder(root, sum, 0)
// 先序遍历二叉树 根左右 计算每条路径上节点的总和，返回true或false
// 传递一个 total 计算当前累加和
function preOrder(root, sum, total){
// 出口 都遍历完了，加和还没有与sum相等，返回false
if(!root) return false
total += root.val
// 当遍历到叶子节点时，正好累加和等于sum时，返回true
if(!root.left && !root.right && sum === total) return true
// 否则的话继续遍历
return preOrder(root.left, sum, total) || preOrder(root.right, sum, total)
}
}时间复杂度 O(N)：最坏的情况是递归每个结点，N为节点数 空间复杂度 O(1)：常数级开销。