leetcode 113. 路径总和 II

大耗子 2021年02月20日 15次浏览

题目: 113. 路径总和 II

113. 路径总和 II

难度中等426收藏分享切换为英文接收动态反馈

给定一个二叉树和一个目标和,找到所有从根节点到叶子节点路径总和等于给定目标和的路径。

说明: 叶子节点是指没有子节点的节点。

示例:
给定如下二叉树,以及目标和 sum = 22

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

返回:

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

解题思路

这道题只是在获取路径总和这道题的基础上加了一个栈的操作。并且不需要之前的剪枝操作。

112. 路径总和

代码

class Solution {
public:
	vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
		vector<vector<int>> ans;
		if (!root) return ans;
		vector<int> stack;
		PathSumCore(root, targetSum, ans, stack);
		return ans;
	}

	void PathSumCore(TreeNode* root, int targetSum, vector<vector<int>>& ans, vector<int>& stack) {
		// 空结点一定返回false
		if (!root) return;
		stack.push_back(root->val);
		// 左右子树为空且 当前结点-目标为0 则true
		if (!root->left && !root->right ){
			if(targetSum - root->val == 0) 
				ans.push_back(stack);
			stack.pop_back();
			return;
		}
		// 有子树则继续遍历
		PathSumCore(root->left, targetSum - root->val, ans, stack);
		PathSumCore(root->right, targetSum - root->val, ans, stack);
		stack.pop_back();
	}
};