[名企面试知识点][Java]二叉树中 和为某值 的所有路径
发布于 2017-03-14 13:54 2439 次浏览 1 赞 来自 笔试面试  

题目描述

输入一颗二叉树和一个整数,打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径

输入描述

一颗二叉树和一个整数

输出描述

二叉树中结点值的和为输入整数的所有路径

题目分析

节点描述:

public class TreeNode {
   int val = 0;
   TreeNode left = null;
   TreeNode right = null;

   public TreeNode(int val) {
       this.val = val;

   }

}

解法  运行时间:31ms 占用内存:652k 

public class Solution {
   //用于存储路径集合
   ArrayList<ArrayList<Integer>> paths=new ArrayList<ArrayList<Integer>>();

   public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {        
       if(root==null) return paths;
       //递归调用
       SearchPath(new ArrayList<Integer>(),root,target);
       return paths;
   }
   public void SearchPath(ArrayList<Integer> path,TreeNode root,int target){
       if(root==null) return;
       //把当前节点加入路径,同时target要减去当前节点的值
       //这里path和target都是值传递的局部变量
       path.add(root.val);
       target=target-root.val;

       if(root.left==null&&root.right==null){
           //target为零的叶子节点对应的路径就是所求路径,把它加入到路径集合中
           if(target==0){
            paths.add(path);
           }
           return;
       }
       //不是叶子节点继续向下遍历,拷贝一个路径
       ArrayList<Integer> path2=new ArrayList<>();
       path2.addAll(path);
       //递归左右节点
       SearchPath(path,root.left,target);
       SearchPath(path2,root.right,target);
   }
}

  递归遍历整棵树,每到一个节点时,把节点加入路径并target减去当前节点的值。如果为叶子节点,判断target是否为零,为零就是一条成功的路径。不是叶子节点就继续向左右子节点遍历。

添加回复
回到顶部