Code More Create

Appearance

Return to top
On this page

34.二叉树中和为某一值的路径

题目描述

给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。

注意：叶子节点 是指没有子节点的节点。

思路分析

  1. 对树进行一次遍历，在遍历时记录从根节点到当前节点的路径和，以防止重复计算。
  2. 本文使用深度优先搜索进行解答，也可以使用广度优先搜索，时间复杂度均为O(n^2)
  3. 其他问题以注释的形式标注在代码中

AC 代码 

class Solution {
    // 记录结果
    public List<List<Integer>> ans = new ArrayList<>();
    // 存储路径
    public List<Integer> list = new ArrayList<>();
    public List<List<Integer>> pathSum(TreeNode root, int target) {
        // 注意这里不需要进行判断，因为结点值有可能是负数
        // if(target == 0) return ans; ❎

        // 从根节点进行遍历
        dfs(root,0,target);
        return ans;
    }
    public void dfs(TreeNode node,int sum,int target){
        // base case 
        if(node == null) return;
        // 添加结点，重新计算num值
        list.add(node.val);
        sum = sum + node.val;
        // 如果满足条件，则把路径加入
        if(node.left == null && node.right == null && sum == target){
            ans.add(new ArrayList<>(list));
            // 注意这里不能return，因为后面还需要把当前结点移除，进行下一次遍历 ❎
        }
        // 继续遍历左右节点
        dfs(node.left, sum, target);
        dfs(node.right, sum, target);
        // 遍历完成后，移除队列中的最后一个结点，也就是本节点
        list.remove(list.size() - 1);
    }
}

总结 

result = []
def backtrack(路径, 选择列表):
    if 满足结束条件:
        result.add(路径)
        return
    
    for 选择 in 选择列表:
        做选择
        backtrack(路径, 选择列表)
        撤销选择

核心思想就是不断往下一层进行遍历；

在进行下一次遍历之前，做判断，如果满足条件，添加结果；

然后做下一步的选择，如何能够到达下一层；

在遍历之后，撤销选择