二叉树中和为某一值的路径(一)

发表于

描述
给定一个二叉树root和一个值 sum ，判断是否有从根节点到叶子节点的节点值之和等于 sum 的路径。

  1. 该题路径定义为从树的根结点开始往下一直到叶子结点所经过的结点
  2. 叶子节点是指没有子节点的节点
  3. 路径只能从父节点到子节点，不能从子节点到父节点
  4. 总节点数目为n

题解

  • 递归

    采用递归遍历二叉树的路径节点，同时计算二叉树路径节点的数字之和，当到达叶子节点且路径的数字之和等于 sum 则说明二叉树中存在节点和为指定值的路径

  1. 特殊情况：当二叉树为空，则返回 false
  2. 遍历根节点的左右子树，记录根节点的数字之和 res，当节点的左右子树均为空，且 res == sum，则返回 true
  3. 递归 该节点的左右子树，做上述计算
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
package main

type TreeNode struct {
    Val int
    Left *TreeNode
    Right *TreeNode
}

/**
  * 
  * @param root TreeNode类 
  * @param sum int整型 
  * @return bool布尔型
*/
func hasPathSum( root *TreeNode ,  sum int ) bool {
    // write code here
    if root == nil {
        return false
    }
    if root.Left == nil && root.Right == nil {
        return root.Val == sum
    }

    return hasPathSum(root.Left, sum-root.Val) || hasPathSum(root.Right, sum - root.Val)
}
  • 深度优先遍历+回溯
  1. 首先，深度优点遍历来说，先写上一个回溯 if (curNode == null) { return false; }，这表示递归至最深层开始回溯
  2. 每次进入函数时，将 sum 减去当前节点的权重(curNode.val)，当 sum 减到零时，说明目标路径存在，另外我们的目标是到叶子节点停止，叶子节点的条件是 curNode.left == null && curNode.right == null，所以说当 if (curNode.left == null && curNode.right == null && target == 0) ，我们返回 true 表示找到目标路径
  3. 深度遍历的分支：对于当前节点 curNode 有两个分支，这两个分支都有可能成为目标路径，所以深度优先遍历的写法为 return dfs(curNode.left, target) || dfs(curNode.right, target)
  4. 现在来谈谈为什么回溯时需要返回 false，因为当 curNode 为叶子节点时，并且 sum == 0 时，我们已经返回了 true，剩下的情况就是 curNode 不是叶子节点或者路径值不为 target，所应该返回 false

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
package main

type TreeNode struct {
    Val int
    Left *TreeNode
    Right *TreeNode
}

/**
 *
 * @param root TreeNode类
 * @param sum int整型
 * @return bool布尔型
 */
func hasPathSum(root *TreeNode, sum int) bool {
	// write code here
	if root == nil {
		return false
	}

	return dfs(root, sum)
}

func dfs(node *TreeNode, target int) bool {
	// 目标路径不存在，开始回溯
	if node == nil {
		return false
	}

	// 更新目标值
	target -= node.Val

	// 当当前节点为叶子节点并且目标路径存在时，返回 true
	if node.Left == nil && node.Right == nil && target == 0 {
		return true
	}
	// 对左右分支进行 dfs
	return dfs(node.Left, target) || dfs(node.Right, target)
}