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

  • 题目描述

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

  • 递归解法
  1. class Solution {
  2. public:
  3.     vector<vector<int>> ret;
  4. 	vector<int> t;
  5. 	vector<vector<int> > FindPath(TreeNode* root, int expectNumber) {
  6. 		TreeNode* p = root;
  7. 		stack<int> s;
  8. 		if (root != NULL)
  9. 			dfs(root, expectNumber);
  10. 		return ret;
  11. 	}
  13. 	void dfs(TreeNode* root, int e){
  14. 		t.push_back(root->val);
  15. 		if (root->left == NULL && root->right == NULL && e-root->val==0)
  16. 			ret.push_back(t);
  17. 		else{
  18. 			if (root->left)
  19. 				dfs(root->left, e-root->val);
  20. 			if (root->right)
  21. 				dfs(root->right, e-root->val);
  22. 		}
  23. 		t.pop_back();
  24. 	}
  25. };
  • 非递归解法

这个非递归还真是有点不太好写。。

  1. class Solution {
  2. public:
  3.     vector<vector<int>> res;
  4. 	vector<vector<int> > FindPath(TreeNode* root, int expectNumber) {
  5. 		TreeNode* p = root;
  6. 		if (root == NULL)
  7. 			return res;
  8. 		stack<TreeNode*> s;
  9. 		s.push(root);
  10. 		int sum = 0;//当前和
  11. 		vector<int> curPath;
  12. 		TreeNode *cur = root;
  13. 		TreeNode *last = NULL;
  15. 		while (!s.empty()){
  16. 			if (cur == NULL){
  17. 				TreeNode* t = s.top();
  18. 				if (t->right != NULL && t->right != last)
  19. 					cur = t->right;//转向未遍历过的右子树
  20. 				else{
  21. 					last = t;//保存上一个已遍历地结点
  22. 					s.pop();
  23. 					curPath.pop_back();//从当前路径删除
  24. 					sum -= t->val;
  25. 				}
  26. 			}
  27. 			else{
  28. 				s.push(cur);
  29. 				sum += cur->val;
  30. 				curPath.push_back(cur->val);
  31. 				if (cur->left == NULL&&cur->right == NULL&&sum == expectNumber)
  32. 					res.push_back(curPath);
  33. 				cur = cur->left;//先序遍历，左子树先于右子树
  34. 			}
  35. 		}
  36. 		return res;
  37. 	}
  38. };
弹钢琴的猫 /
Published under (CC) BY-NC-SA in categories 算法  tagged with 剑指offer  Tree