金融AIGC研究
搜索
优质  高效     
优质的技术交付服务 迅捷的办事效率
我们专注品质与服务   决胜制高点  细节决定成败
Runoff commanding heights Detail decides success or failure
The commanding heights of
the details determine success or failure
技术动态
DETAIL
Leetcode 学习第二天
来源:互联网 | 作者:business-101 | 发布时间: 2024-03-18 | 258 次浏览 | 分享到:

https://datawhalechina.github.io/leetcode-notes/#/ch07/07.02/07.02.01-Exercises?id=_1-0112-%e8%b7%af%e5%be%84%e6%80%bb%e5%92%8c

遍历二叉树， 并求和

1.0112. 路径总和

/**
 * Definition for a binary tree node.
 * 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;
 *     }
 * }
 */
class Solution {
    public boolean gsum(TreeNode ll,int cur,int fi){
            cur+=ll.val;
        if(ll.left!=null&&ll.right!=null){
            return gsum(ll.left,cur,fi)||gsum(ll.right,cur,fi);
        }else if(ll.left==null&&ll.right==null){
            return cur==fi;
        }else if(ll.left==null){
            return gsum(ll.right,cur,fi);

        }else{
            return gsum(ll.left,cur,fi);

        }
    }
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if(root==null)return false;
        return gsum(root,0,targetSum);
    }
}



2.0113. 路径总和 II

主要采用遍历算法， 及克隆运算

/**
 * Definition for a binary tree node.
 * 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;
 *     }
 * }
 */
class Solution {

    public void gsum(TreeNode ll,int cur,int fi,List<Integer> tl,List<List<Integer>> ret){
            cur+=ll.val;
        if(ll.left!=null&&ll.right!=null){
            tl.add(ll.val);
            List<Integer> tr=tl.stream().collect(Collectors.toList());
            gsum(ll.left,cur,fi,tl,ret);
            gsum(ll.right,cur,fi,tr,ret);
        }else if(ll.left==null&&ll.right==null){
            if(cur==fi){tl.add(ll.val);ret.add(tl);}
            return;
        }else if(ll.left==null){
            tl.add(ll.val);
            gsum(ll.right,cur,fi,tl,ret);

        }else{
            tl.add(ll.val);
            gsum(ll.left,cur,fi,tl,ret);

        }
    }

    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        List<List<Integer>> ret=new ArrayList<>();
        if(root==null)return ret;

        gsum(root,0,targetSum,new ArrayList<Integer>(),ret);
        return ret;
    }
}