美文网首页数据结构与算法
Leetcode 112 路径总和

Leetcode 112 路径总和

作者: itbird01 | 来源:发表于2021-12-19 00:09 被阅读0次

    112. 路径总和

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

    解题思路

    解法1:递归
    1.假设当前节点为k,根节点到当前节点的和为val,那么如果有叶子节点满足targetSum的话,一定满足条件:根节点到当前节点的和==targetSum-当前节点的下一节点到叶子节点的和
    2.递归还有一个重要条件需要找到,即结束条件,我们知道叶子节点的判断条件为:root.left == null && root.right == null
    3.由1推导可知,如果此时的叶子节点满足条件,一定满足条件current.val == vSum,这里的vSum实际上前面targetSum一直在递归过程中,减去叶子节点之前的节点的差,即vSum=targetSum-current上面所有节点值

    解题遇到的问题

    后续需要总结学习的知识点

    需要深入总结学习DFS/BFS/递归/迭代 与队列、栈的相互关系

    ##解法1
    class Solution {
        public boolean hasPathSum(TreeNode root, int targetSum) {
            if (root == null) {
                return false;
            }
    
            if (root.left == null && root.right == null) {
                return root.val == targetSum;
            }
    
            return hasPathSum(root.left, targetSum - root.val)
                    || hasPathSum(root.right, targetSum - root.val);
        }
    
        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;
            }
        }
    }
    

    相关文章

      网友评论

        本文标题:Leetcode 112 路径总和

        本文链接:https://www.haomeiwen.com/subject/yfjgfrtx.html