257. 二叉树的所有路径——113.路径总和II_面试题34. 二叉树中和为某一值的路径_matlab 给定二叉树和每条边的权值,求每条路径的权值和-CSDN博客

本文链接：https://blog.csdn.net/puspos/article/details/104074441

这篇博客主要探讨了两道关于二叉树路径总和的问题：257题和面试题34（113题）。对于257题，文章解释了如何找到从根节点到叶子节点的所有路径，并给出了具体代码实现。在113题中，博客内容关注于寻找和为目标值的路径。通过递归方法，解决了在遍历过程中保持路径完整性的挑战。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

257. 二叉树的所有路径

问题

例子

代码

//回溯
class Solution {
    public List<String> binaryTreePaths(TreeNode root) {
        
        List<String> list = new ArrayList<>();
        preOrder(root,list,new StringBuilder());
        return list;
    }
    //为null是才return
    public void preOrder(TreeNode root, List<String> list, StringBuilder sb) 
    {
        if(root==null) return;
        int len = sb.length();
        if(sb.length()!=0) {
            sb.append("->");
        }
        sb.append(root.val);
       
        if(root.left==null && root.right==null) {//如果为叶节点
            list.add(sb.toString());
			//找到添加的东西时，可以直接return，进行剪枝，但是要先将sb进行回溯
			//sb.delete(len,sb.length());
			//return;
        }else{
            if(root.left!=null) preOrder(root.left,list,sb);
            if(root.right!=null) preOrder(root.right,list,sb);
        }
                
        sb.delete(len, sb.length());
        
        
    }
}

113.路径总和II_面试题34. 二叉树中和为某一值的路径

问题
给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。
例子
在这里插入图片描述
思路
方法(root，变化的sum，二维数组res，路径list）

方法1
如何保存根节点到叶节点的路径？get()方法中要带有数组list，因为要先后get(左子树)，get(右子树)，所以两个数组不能有牵扯，get(左子树)对list进行了修改，会直接影响传入get(右子树)的list
所以：对某结点，get(左子树)时复制一个list，get(右子树)时复制一个list
方法2：方法1中创建新数组太多了，只复制需要的路径。
用li保存访问的结点的值（路径），访问完该结点：
如果正好为叶节点且到其值正好为sum，复制li并加入二维数组res
否则访问左右子树
最后将该值从li中弹出
代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
//方法1
class Solution {
    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> list = new ArrayList<>();
        if(root==null) return res;
        
        get(root,sum,res,list);
        return res;
    }
    public void get(TreeNode root, int sum, List<List<Integer>> res, List<Integer> list) {
        if (root==null) return ;
        list.add(root.val);
        if (root.left==null && root.right==null && root.val==sum) {
            
            res.add(list);
            return;
        }
        
        sum-=root.val;
        get(root.left, sum, res, new ArrayList<Integer>(list));
        get(root.right, sum, res, new ArrayList<Integer>(list));

        
    }
}
//方法2
class Solution {
    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        
        List<List<Integer>> list = new ArrayList<>();
        if(root==null) return list;
        get(root,list,new ArrayList<Integer>(),sum);
        return list;
    }
    
    public void get(TreeNode root, List<List<Integer>> list, List<Integer> temp_list, int sum) {
        if(root==null) return;
        temp_list.add(root.val);
        if(root.left==null && root.right==null && root.val==sum)
            list.add(temp_list);
        else{
            get(root.left,list,temp_list,sum-root.val);
            get(root.right,list,temp_list,sum-root.val);
            
        }
        temp_list.remove(temp_list.size()-1);
    }
}

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

# 方法1
class Solution:
    
    def pathSum(self, root: TreeNode, sum: int) -> List[List[int]]:
        res=list()
        li=list()
        if root is None: return res
        self.get(root,sum,res,li)
        return res
    def get(self,root,sum,res,li):
        if root is None: return None
        li.append(root.val)
        if root.left is None and root.right is None and sum==root.val:
            res.append(li)
            return None
        sum-=root.val
        self.get(root.left,sum,res,copy.copy(li)) 
        self.get(root.right,sum,res,copy.copy(li))
#方法2
class Solution:
    def pathSum(self, root: TreeNode, sum: int) -> List[List[int]]:
        res=list()
        li=list()
        
        if root is None: return res
        self.get(root,sum,res,li)
        return res
    def get(self, root, sum, res, li):
        if root is None: return None
        li.append(root.val)
        if root.left is None and root.right is None and root.val==sum:
            res.append(copy.copy(li))
            #return None 可能结束，因为还没有返回
        else:
            sum-=root.val
            self.get(root.left,sum,res,li)
            self.get(root.right,sum,res,li)
        
        li.pop()