LeetCode 112. 路径总和 && 广度优先搜索|二叉树递归

题目要求

原题目链接：112. 路径总和

题目要求如下：

给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。

叶子节点 是指没有子节点的节点。

示例如下：

示例1：>输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
输出：true
解释：等于目标和的根节点到叶节点路径如上图所示。
示例2：

输入：root = [1,2,3], targetSum = 5
输出：false
解释：树中存在两条根节点到叶子节点的路径：
(1 --> 2): 和为 3
(1 --> 3): 和为 4
不存在 sum = 5 的根节点到叶子节点的路径。

TreeNode定义如下：

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

解法1：广度优先搜索

思路

题目要求找出二叉树中是否存在，从根节点root到叶子节点的路径和等于targetSum的路径，

最容易想到的方法就是对二叉树进行遍历，累加每个节点的val值，并与targetSum进行比较。实现上采用两个队列，一个用于存放节点，一个用于存放节点的累加值，如果不在意原树的val值是否会被修改，可以不使用额外空间记录节点累加值，直接累加到子节点的val值即可。

完整AC代码

class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if(root == null) return false;
        Queue<TreeNode> node = new LinkedList<>();
        Queue<Integer> val = new LinkedList<>();
        node.offer(root);
        val.offer(root.val);
        while(!node.isEmpty()){
            TreeNode cur = node.poll();
            int curval = val.poll();
            // 叶子节点
            if(cur.left == null && cur.right == null){
                if(curval == targetSum) return true;
                continue;
            }
            // 向队列添加子树
            if(cur.left != null){
                node.offer(cur.left);
                // 值累加
                val.offer(cur.left.val + curval);
            }
            if(cur.right != null){
                node.offer(cur.right);
                val.offer(cur.right.val + curval);
            }
        }
        // 遍历二叉树仍没有满足条件的路径和 返回false
        return false;
    }
}

复杂度分析

时间复杂度：O(N)，N为二叉树中节点数，时间复杂度等同于一次二叉树遍历。
空间复杂度：O(N)，需要额外的队列来存储节点和累加值，额外存放的节点最多不会超过二叉树中节点，故空间复杂度O(N)。

解法1：递归

思路

想判断路径和是否等于targetSum，不一定非要使用累加后比较的方法，也可以每访问一个节点使targetSum - val，这样就将大问题转换为了小问题，使用递归可以解决，只需要做参数传递，不需要额外空间记录信息。

完整AC代码

class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
    	// 为空直接返回
        if(root == null) return false;
        // 左右子树都为null 说明到了叶子节点
        if(root.left == null && root.right == null) return root.val == targetSum;
        // 递归调用 传入左右子树 有任一子树满足条件就满足题目要求
        return hasPathSum(root.left, targetSum - root.val) || hasPathSum(root.right, targetSum - root.val);
    }
}

复杂度分析

时间复杂度：O(N)，N为二叉树中节点数，时间复杂度等同于一次二叉树遍历。
空间复杂度：O(H)，H为树的高度。不使用额外空间，但递归会产生栈空间开销，递归深度取决于树的高度。