本文共 1050 字,大约阅读时间需要 3 分钟。
输入一颗二叉树和一个整数,打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。
下图的二叉树有两条和为 22 的路径:10, 5, 7 和 10, 12
package cn.cqu.edu;import java.util.ArrayList;public class Find_Path { class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; } } ArrayList> ret=new ArrayList<>(); private void result(TreeNode root,int target, ArrayList arrayList) { //注意栈变量和引用变量在这里起的作用,很微妙 if(root==null) { return; } target=target-root.val; arrayList.add(root.val); if(target==0 && root.left==null && root.right==null) { ret.add(new ArrayList<>(arrayList)); //因为arrayList是引用类型,因此用new创建一块新的存储空间,此块空间用arrayList初始化 } else { result(root.left,target,arrayList); result(root.right,target,arrayList); } arrayList.remove(arrayList.size()-1); } public ArrayList > FindPath(TreeNode root,int target) { result(root,target,new ArrayList<>()); return ret; } public static void main(String[] args) { }}
转载地址:http://wckmi.baihongyu.com/