LeetCode 113. Path Sum II

LeetCode 113. Path Sum II

Description:

Given a binary tree and a sum, find all root-to-leaf paths where each path’s sum equals the given sum.

Example:

For example:
Given the below binary tree and sum = 22,

      5
     / \
    4   8
   /   / \
  11  13  4
 /  \    / \
7    2  5   1

return

[
   [5,4,11,2],
   [5,8,4,5]
]

---

分析：

如果采用栈去深度优先遍历解决，难度是比较大的，Discuss上面有一种解法采用了一个一维数组vector来存储一条路径，如果找到一条路径上的和等于sum的话，就将这个一维数组添加到二维数组中去。

同样，代码首先判断根节点是否为空，为空直接返回空二维数组。

不空时，将根节点加入到一维数组path中，然后判断左右子树是否为空，为空时判断根节点的数是否等于sum，若为真返回该path（只有根节点：一个节点一条路径）。

若左右子树不空时，递归左右子树。

注意最后有个路径回溯path.pop_back();

代码如下：

#include <iostream>
#include <vector>
using namespace std;
/**
 * Definition for a binary tree node.
 */
struct TreeNode {
	int val;
	TreeNode *left;
	TreeNode *right;
	TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
	vector<vector<int> > pathSum(TreeNode* root, int sum) {
		vector<vector<int> > paths;
		vector<int> path;
		findPaths(root, sum, path, paths);
		return paths;
	}
private:
	void findPaths(TreeNode* node, int sum, vector<int>& path, vector<vector<int> >& paths) {
		if (node == NULL) return;
		path.push_back(node->val);
		if (node->left == NULL && node->right == NULL && sum == node->val)
			paths.push_back(path);
		findPaths(node->left, sum - node->val, path, paths);
		findPaths(node->right, sum - node->val, path, paths);
		path.pop_back();
	}
};
// 构造二叉树
int TreeNodeCreate(TreeNode* &tree) {
	int val;
	cin >> val;
	if (val < 0) // 小于0表示空节点
		tree = NULL;
	else {
		tree = new TreeNode(val); // 创建根节点
		tree->val = val;
		TreeNodeCreate(tree->left); // 创建左子树
		TreeNodeCreate(tree->right);// 创建右子树
	}
	return 0;
}
int main() {
	Solution s;
	TreeNode* tree;
	TreeNodeCreate(tree);
	int sum;
	cin >> sum;
	vector<vector<int> > res = s.pathSum(tree, sum);
	for (int i = 0; i < res.size(); i++) {
		for (int j = 0; j < res[i].size(); j++) {
			cout << res[i][j] << " ";
		}
		cout << endl;
	}
	return 0;
}
/*
input:
5
4
11
7
-1 -1
2
-1 -1
-1
8
13
-1 -1
4
5
-1 -1
1
-1 -1

22

output:
5 4 11 2
5 8 4 5
 */