剑指offer--二叉树中和为某一值的路径
题目描述 输入一颗二叉树和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。
思路： 1. 如果根节点为空或根节点的值大于target则返回空， 2. 否则进入寻找路径的函数，如果根结点的值等于target那么判断如果右子树为空则把根节点的值假如path，反之清空path。 3.若根结点的值不等于target，那么复制path数组到rightpath，之后用path递归执行左子树，rightpath递归执行右子树。
Java AC代码：
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 {
public void findpath(TreeNode root,int target,ArrayList<ArrayList<Integer>> paths,ArrayList<Integer> path){
if(root == null || root.val > target){
path.clear();
}else if(root.val == target){
if(root.left == null && root.right == null){
path.add(root.val);
paths.add(path);
}else{
path.clear();
}
}else{
path.add(root.val);
ArrayList<Integer> rightpath = new ArrayList<>();
rightpath.addAll(path);
target -= root.val;
findpath(root.left, target, paths,path);
findpath(root.right, target, paths,rightpath);
}
}
public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
ArrayList<Integer> path = new ArrayList<>();
ArrayList<ArrayList<Integer>> paths = new ArrayList<>();
if(root == null || root.val > target){
return paths;
}
findpath(root, target,paths,path);
return paths;
}
}C++ AC代码：
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};
class Solution {
public:
vector<vector<int> > FindPath(TreeNode* root,int expectNumber) {
vector<vector<int> > ans;
vector<int> tmp;
if(root == NULL || root->val > expectNumber){
return ans;
}
this->findpath(root,expectNumber,tmp,ans);
return ans;
}
void findpath(TreeNode* root,int expectNumber,vector<int>& path,vector<vector<int> >& paths){
if(root == NULL || root->val > expectNumber){
path.clear();
}else if(root->val == expectNumber){
if(root->left == NULL && root->right == NULL){
path.push_back(root->val);
paths.push_back(path);
}else{
path.clear();
}
}else{
path.push_back(root->val);
expectNumber -= root->val;
vector<int> right;
for(int i = 0 ; i < path.size() ; i++){
right.push_back(path[i]);
}
this->findpath(root->left,expectNumber,path,paths);
this->findpath(root->right,expectNumber,right,paths);
}
}
};本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读