您现在的位置是:首页 > 文章详情

[剑指offer] 二叉树中和为某一值的路径

日期:2018-06-30点击:312

题目描述

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

解题思路

用前序遍历的方式访问到某一结点时,把该结点添加到路径上,并用目标值减去该节点的值。如果该结点为叶结点并且目标值减去该节点的值刚好为0,则当前的路径符合要求,我们把加入res数组中。如果当前结点不是叶结点,则继续访问它的子结点。当前结点访问结束后,递归函数将自动回到它的父结点。因此我们在函数退出之前要在路径上删除当前结点,以确保返回父结点时路径刚好是从根结点到父结点的路径。

参考代码

import java.util.ArrayList; /** public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; } } */ public class Solution { ArrayList<ArrayList<Integer> > res = new ArrayList<ArrayList<Integer> >(); ArrayList<Integer> temp = new ArrayList<Integer>(); public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) { if(root == null) return res; target -= root.val; temp.add(root.val); if(target == 0 && root.left == null && root.right == null) res.add(new ArrayList<Integer>(temp)); else{ FindPath(root.left, target); FindPath(root.right, target); } temp.remove(temp.size()-1); return res; } } 
原文链接:https://yq.aliyun.com/articles/642787
关注公众号

低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。

持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。

转载内容版权归作者及来源网站所有,本站原创内容转载请注明来源。

文章评论

共有0条评论来说两句吧...

文章二维码

扫描即可查看该文章

点击排行

推荐阅读

最新文章