首页 / 算法 / 算法-01-二叉树根节点到叶子节点和为指定值的路径

算法-01-二叉树根节点到叶子节点和为指定值的路径

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了算法-01-二叉树根节点到叶子节点和为指定值的路径，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1750字，纯文字阅读大概需要3分钟。

内容图文

描述

给定一个二叉树和一个值sum，请找出所有的根节点到叶子节点的节点值之和等于sum 的路径， 例如： 给出如下的二叉树，sum=22

技术分享图片

Java 

            import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */publicclass Solution {
    /**
     * 
     * @param root TreeNode类 
     * @param sum int整型 
     * @return int整型ArrayList<ArrayList<>>
     */
    ArrayList<ArrayList<Integer>> results= new ArrayList<>();
    
    public ArrayList<ArrayList<Integer>> pathSum (TreeNode root, int sum) {
        // write code here
        ArrayList<Integer> path =new ArrayList<>();
        if(root==null)
            return results;
        dfs(root,0,sum,path);
        return results;
    }
    
    publicvoid dfs(TreeNode root,int nowSum, int sum, ArrayList<Integer> list){
        list.add(root.val);
        if(root.right==null&&root.left==null&&sum==nowSum+root.val){
            results.add(new ArrayList<>(list));
            return;
        }
        if(root.left!=null){
            dfs(root.left,nowSum+root.val,sum,list);
            list.remove(list.size()-1);
        }
        if(root.right!=null){
            dfs(root.right, nowSum+root.val,sum,list);
            list.remove(list.size()-1);
        }
    }
}

 Python 

            #
             class TreeNode:
            
#
                 def __init__(self, x):
            
#
                     self.val = x
            
#
                     self.left = None
            
#
                     self.right = None
            #
#
            
#
             @param root TreeNode类 
            
#
             @param sum int整型 
            
#
             @return int整型二维数组
            
#

            class
             Solution:
    
            def
             pathSum(self , root , sum ):
        
            #
             write code here
        path = []
        paths = []
        self.dfs(root,sum,path,paths)
        return paths
        
    def dfs(self, root: TreeNode, sum :int, path: list, paths: list):
        if root is None:
            return None
        path.append(root.val)
        if root.left is None and root.right is None and sum==root.val:
            paths.append(path.copy())
        else:
            self.dfs(root.left,sum-root.val,path,paths)
            self.dfs(root.right,sum-root.val,path,paths)
        path.pop(len(path)-1)

 

原文：https://www.cnblogs.com/shix0909/p/15028414.html

内容总结

以上是互联网集市为您收集整理的算法-01-二叉树根节点到叶子节点和为指定值的路径全部内容，希望文章能够帮你解决算法-01-二叉树根节点到叶子节点和为指定值的路径所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/1104721.html

来源：【匿名】