剑指offer—二叉树路径总和 解答

剑指offer—二叉树路径总和

题目描述

给定一个二叉树和一个目标和,判断该树中是否存在根节点到叶子节点的路径,这条路径上所有节点值相加等于目标和。

说明: 叶子节点是指没有子节点的节点。

示例: 
给定如下二叉树,以及目标和 sum = 22,

              5
             / \
            4   8
           /   / \
          11  13  4
         /  \      \
        7    2      1
返回 true, 因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/path-sum
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

思路

使用递归遍历二叉树,参数传入自己的值加上下一个节点的值,如果等于target的值递归结束,把标志成功变量致为1,直接返回(后面的情况不用考虑,直接返回true),遍历完二叉树没有找到这样的路径则使用初始值0,1时返回true,0时返回false

步骤:

  • 如果为空二叉树,返回false
  • 递归
    • 如果累加的值为target的目标值,并且左右子树为空(说明叶子节点),s=1;并返回
    • 否则如果左子树不为空,递归遍历左子数,参数中的val加上左子树的val
    • 如果右子树不为空,还需递归右子树
  • 判断s的值并返回结果

代码

class Solution {
    int s = 0;
    public boolean hasPathSum(TreeNode root, int target) {
        if(root==null) return false;
        dfs(root,root.val,target);
        if(s==1) return true;
        return false;
    }

    public void dfs(TreeNode node,int val,int target){
        //if(node==null) return false;
        if(val==target&&node.left==null&&node.right==null) {s = 1;return;}
        if(node.left!=null) dfs(node.left,val+node.left.val, target);
        if(node.right!=null) dfs(node.right,val+node.right.val, target);
    }
}

扩展—输出所有满足总和路径的列表

leetcode-113

题目描述

给定一个二叉树和一个目标和,找到所有从根节点到叶子节点路径总和等于给定目标和的路径。

说明: 叶子节点是指没有子节点的节点。

示例:
给定如下二叉树,以及目标和 sum = 22,

              5
             / \
            4   8
           /   / \
          11  13  4
         /  \    / \
        7    2  5   1
返回:

[
   [5,4,11,2],
   [5,8,4,5]
]

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/path-sum-ii
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

思路

判断方式与上面一致,我们已经能找到路径,重点是如何把路径上的元素添加到集合中并且维护集合

我们知道如果每次用同一个集合在递归中添加新的元素,那么集合中会出现不再同一路径下的元素,我们要如何维护这个集合呢?

代码

class Solution {
    List<List<Integer>> list = new ArrayList<>();//总集合
    List<Integer> cp = new ArrayList<>();//当前路径集合
    public List<List<Integer>> pathSum(TreeNode root, int target) {
        if(root==null) return list;
        dfs(root,root.val,target);//递归
        return list;
    }
    public void dfs(TreeNode node,int val,int target){
        if(node==null) return;
        cp.add(node.val);
        //这里使用new ArrayList创建新的列表是因为cp需要被修改,如果你添加同一个cp,它的修改在list中是可见的
        if(val==target&&node.left==null&&node.right==null) list.add(new ArrayList(cp));
        if(node.left!=null) dfs(node.left,val+node.left.val, target);//递归左子树
        if(node.right!=null) dfs(node.right,val+node.right.val, target);//递归右子树
        //每次执行到这说明一个分支结束了,把cp中最后一个元素删除,也就是将进入下一个路径
        cp.remove(cp.size()-1);
    }
}
  • 本文作者: dzou | 微信:17856530567
  • 本文链接: http://www.dzou.top/post/sum-btree-path.html
  • 版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明出处!
  • 并保留本声明和上方二维码。感谢您的阅读和支持!