257. 二叉树的所有路径

谁借莪１个温暖的怀抱￠ 2024-03-31 14:12 71阅读 0赞

### 257. 二叉树的所有路径 ###

给你一个二叉树的根节点 root ，按 **任意顺序** ，返回所有从根节点到叶子节点的路径。

叶子节点 是指没有子节点的节点。

##### 示例 1： #####

![在这里插入图片描述][03a185fed29e4a6e8cf193b4a5ddf024.png]

> 输入：root = \[1,2,3,null,5\]  
> 输出：\[“1->2->5”,“1->3”\]

##### 示例 2： #####

> 输入：root = \[1\]  
> 输出：\[“1”\]

##### 提示： #####

树中节点的数目在范围 \[1, 100\] 内  
\-100 <= Node.val <= 100

#### 思路：（回溯） ####

注意:

*  因为每个结点的值的长度，不同，要考虑使用什么方法在回溯的过程中准确添加和删除该值

#### 代码：（Java） ####

**方法一：**

import java.util.ArrayList;
    import java.util.List;
    
    public class binary_tree_paths {
        
    	 public static 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 void main(String[] args) {
        
    		// TODO 自动生成的方法存根
    		//int [] node = {1,2,3,null,5};
    		TreeNode root = new TreeNode(1);
    		root.left = new TreeNode(2);
    		root.right = new TreeNode(3);
    		root.left.right = new TreeNode(5);
    		System.out.println(binaryTreePaths(root));
    		
    	} 
    	public static List<String> binaryTreePaths(TreeNode root) {
        
    		List<String> ret = new ArrayList<>();
    		if(root == null) {
        
    			return ret;
    		}
    		StringBuffer path = new StringBuffer();
    		path.append(root.val);
    		
    		backtracking(path,ret,root);
    		return ret;
        }
    	private static void backtracking(StringBuffer path, List<String> ret, TreeNode root) {
        
    		// TODO 自动生成的方法存根
    		if(root.left == null && root.right == null) {
        
    			ret.add(path.toString());
    			return;
    		}
    		if(root.left != null) {
        
    			TreeNode lroot = root.left;
    			int start = path.length();
    			path.append("->" + lroot.val);
    			int end = path.length();
    			backtracking(path,ret,lroot);
    			path.delete(start, end);
    		}
    		if(root.right != null) {
        
    			TreeNode rroot = root.right;
    			int start = path.length();
    			path.append("->" + rroot.val);
    			int end = path.length();
    			backtracking(path,ret,rroot);
    			path.delete(start, end);
    		}
    		
    	}
    
    }

**方法二：**

import java.util.ArrayList;
    import java.util.List;
    
    public class binary_tree_paths {
        
    	 public static 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 void main(String[] args) {
        
    		// TODO 自动生成的方法存根
    		//int [] node = {1,2,3,null,5};
    		TreeNode root = new TreeNode(1);
    		root.left = new TreeNode(2);
    		root.right = new TreeNode(3);
    		root.left.right = new TreeNode(5);
    		System.out.println(binaryTreePaths(root));
    		
    	} 
    	
    	public static List<String> binaryTreePaths(TreeNode root) {
        
    	    List<String> paths = new ArrayList<>();
    	    if (root == null) {
        
    	        return paths;
    	    }
    	    List<Integer> values = new ArrayList<>();
    	    backtracking(root, values, paths);
    	    return paths;
    	}
    	
    	private static void backtracking(TreeNode node, List<Integer> values, List<String> paths) {
        
    	    if (node == null) {
        
    	        return;
    	    }
    	    values.add(node.val);
    	    if (isLeaf(node)) {
        
    	        paths.add(buildPath(values));
    	    } else {
        
    	        backtracking(node.left, values, paths);
    	        backtracking(node.right, values, paths);
    	    }
    	    values.remove(values.size() - 1);
    	}
    	
    	private static boolean isLeaf(TreeNode node) {
        
    	    return node.left == null && node.right == null;
    	}
    	
    	private static String buildPath(List<Integer> values) {
        
    	    StringBuilder str = new StringBuilder();
    	    for (int i = 0; i < values.size(); i++) {
        
    	        str.append(values.get(i));
    	        if (i != values.size() - 1) {
        
    	            str.append("->");
    	        }
    	    }
    	    return str.toString();
    	}
    }

##### 输出: #####

![在这里插入图片描述][e0b2005d8ccc4c7aaa40a6cf0e6a9dc7.png]

##### 注：仅供学习参考！ #####

题目来源：[力扣][Link 1]

[03a185fed29e4a6e8cf193b4a5ddf024.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/51ec87c994db40fb83332394045350bc.png
[e0b2005d8ccc4c7aaa40a6cf0e6a9dc7.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/302a43af9e1948b2ae8b3bddead231b3.png
[Link 1]: https://leetcode.cn/problems/binary-tree-paths/description/