[LeetCode] 113. Path Sum II

轉自LeetCode

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

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]
]

<Solution>

這題是 Path Sum 衍生題

不同點在於，這次不是找到是否有 path sum 能符合就好

而是如果有，要把所有的 path 都找出來

因為要找到所有 path，代表要回溯，所以先想到的是 recursive 的解法

解題想法和 Path Sum 一樣，只是要把過程中經過的值記錄下來，並且配合 recursive 做回溯

code 如下
c++

	/**
	* 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 {
	private:
	vector<int> out;
	vector<vector<int>> ans;
	public:
	vector<vector<int>> pathSum(TreeNode* root, int sum) {
	if(!root) {
	return ans;
	}
	//> use dfs to find all the answer
	dfs(root, sum);
	return ans;
	}
	void dfs(TreeNode* root, const int &sum) {
	if(!root) {
	return;
	}
	out.push_back(root->val);
	if(!root->left && !root->right && root->val == sum) {
	ans.push_back(out);
	out.pop_back();
	return;
	}
	dfs(root->left, sum - root->val);
	dfs(root->right, sum - root->val);
	out.pop_back();
	}
	};

view raw pathSumOfBinaryTreeII_1.cpp hosted with ❤ by GitHub

kotlint

	/**
	* Example:
	* var ti = TreeNode(5)
	* var v = ti.`val`
	* Definition for a binary tree node.
	* class TreeNode(var `val`: Int) {
	* var left: TreeNode? = null
	* var right: TreeNode? = null
	* }
	*/
	class Solution {
	private val ans = mutableListOf<List<Int>>()
	fun pathSum(root: TreeNode?, targetSum: Int): List<List<Int>> {
	dfs(root, targetSum, emptyList())
	return ans
	}
	fun dfs(node: TreeNode?, targetSum: Int, cmb: List<Int>) {
	return when {
	node == null -> return
	node!!.left == null && node!!.right == null -> {
	if(node!!.`val` == targetSum) {
	ans.add(cmb + listOf(node!!.`val`))
	}
	return
	}
	else -> {
	dfs(node!!.left, targetSum - node!!.`val`, cmb + listOf(node!!.`val`))
	dfs(node!!.right, targetSum - node!!.`val`, cmb + listOf(node!!.`val`))
	}
	}
	}
	}

view raw path_sum.kt hosted with ❤ by GitHub

和 Path Sum 一樣，有 iterative 的解法，思路也一樣，差別只在於 queue 要存的資訊而已

這邊注意一點是，因為是先檢查 left node，再檢查 right node

所以如果有先 push left node 的值的話，記得也要 pop 掉

不然在 right node 的部分，會多包含到 left node 的值

code 如下

	/**
	* 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>> ans;
	if(!root) {
	return ans;
	}
	queue<tuple<TreeNode *, vector<int>, int>> nodeQue;
	nodeQue.push(make_tuple(root, vector<int>(1,root->val), root->val));
	while(!nodeQue.empty()) {
	TreeNode *tmpNode;
	vector<int> out;
	int pathSum;
	tie(tmpNode, out, pathSum) = nodeQue.front();
	nodeQue.pop();
	if(!tmpNode->left && !tmpNode->right && pathSum == sum) {
	ans.push_back(out);
	}
	if(tmpNode->left) {
	out.push_back(tmpNode->left->val);
	nodeQue.push(make_tuple(tmpNode->left, out, pathSum+tmpNode->left->val));
	//> because we check left node first, so need to pop_back() here
	//> otherwise, right node will have extra value of previous left node
	out.pop_back();
	}
	if(tmpNode->right) {
	out.push_back(tmpNode->right->val);
	nodeQue.push(make_tuple(tmpNode->right, out, pathSum+tmpNode->right->val));
	}
	}
	return ans;
	}
	};

view raw pathSumOfBinaryTreeII_2.cpp hosted with ❤ by GitHub