二叉树中和为某一值的路径 牛客网 程序员面试金典 C++ Python

二叉树中和为某一值的路径 牛客网 程序员面试金典

题目描述输入一颗二叉树的跟节点和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。(注意: 在返回值的list中，数组长度大的数组靠前)

c++

/* struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) { } };*/ class Solution { public: //run:3ms memory:484k vector<vector<int>> FindPath(TreeNode* root, int expectNumber){ vector<vector<int>> ret; vector<int> lt; if (NULL == root) return ret; return FindAPath(root,expectNumber,ret,lt); } vector<vector<int>> FindAPath(TreeNode* root, int expectNumber, vector<vector<int>> &path_list,vector<int> lt){ if (NULL == root) return path_list; expectNumber -= root->val; lt.push_back(root->val); if (expectNumber != 0){ FindAPath(root->left,expectNumber,path_list,lt); FindAPath(root->right,expectNumber,path_list,lt); }else if(NULL == root->left && NULL == root->right) path_list.push_back(lt); return path_list; } //run:3ms memory:480k vector<vector<int> > FindPath2(TreeNode* root,int expectNumber){ if(root) dfsFind(root, expectNumber); return allRes; } void dfsFind(TreeNode * node , int target){ tmp.push_back(node->val); if(!node->left && !node->right){ if(target - node->val == 0) allRes.push_back(tmp); }else{ if(node->left) dfsFind(node->left, target - node->val); if(node->right) dfsFind(node->right, target - node->val); } if(!tmp.empty()) tmp.pop_back(); } private: vector<vector<int> >allRes; vector<int> tmp; };

Python

# class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: # run:32ms memory:5736k def FindPath(self, root, expectNumber): if None == root: return [] return self.FindAPath(root,expectNumber,[],[]) def FindAPath(self,root,expectNumber,path_list,lt): if None == root: return expectNumber = expectNumber - root.val lt.append(root.val) if expectNumber !=0: left_lt = list(lt) self.FindAPath(root.left,expectNumber,path_list,left_lt) right_lt = list(lt) self.FindAPath(root.right,expectNumber,path_list,right_lt) elif root.left == None and root.right == None: path_list.append(lt) return path_list

 

转载于:https://www.cnblogs.com/vercont/p/10210337.html

相关资源：JAVA上百实例源码以及开源项目