栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

二叉树的路径总和

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

二叉树的路径总和

题目

力扣链接:路径总和
力扣链接:路径总和II

代码

路径总和

package com.harrison.class08;


public class Code11_PathSum {
    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;
        }
    }

    public static boolean isSum=false;

    public static void process(TreeNode x,int preSum,int sum){
        if(x.left==null && x.right==null){
            if(x.val+preSum==sum){
                isSum=true;
            }
            return ;
        }
        preSum+=x.val;
        if(x.left!=null){
            process(x.left,preSum,sum);
        }
        if(x.right!=null){
            process(x.right,preSum,sum);
        }
    }

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

路径总和II

package com.harrison.class08;

import java.util.ArrayList;
import java.util.List;


public class Code12_PathSumII {
    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;
        }
    }

    public static List> pathSum(TreeNode root, int targetSum) {
        List> ans=new ArrayList<>();
        if(root==null){
            return ans;
        }
        List path=new ArrayList<>();
        process(root,path,0,targetSum,ans);
        return ans;
    }

    // path:之前已经形成的路径和的路径
    // preSum:之前已经形成的路径和
    // sum:要求凑够的目标
    // ans:已经找到的答案
    public static void process(TreeNode x,List path,int preSum,int sum,List> ans){
        if(x.left==null && x.right==null){
            if(x.val+preSum==sum){
                path.add(x.val);
                ans.add(copy(path));
                path.remove(path.size()-1);// 经典的恢复现场
            }
            return ;
        }
        path.add(x.val);
        preSum+=x.val;
        if(x.left!=null){
            process(x.left,path,preSum,sum,ans);
        }
        if(x.right!=null){
            process(x.right,path,preSum,sum,ans);
        }
        path.remove(path.size()-1);
    }

    public static List copy(List list){
        List ans=new ArrayList<>();
        for(Integer i:list){
            ans.add(i);
        }
        return ans;
    }
}
转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/981011.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号