做前端常用的网站及软件,南戴河区网站建设哪家好,主机网站建设,惠州seo报价目录 257. 二叉树的所有路径题目描述题目分析cpp代码 112. 路径总和题目描述题目分析cpp代码 257. 二叉树的所有路径
题目描述
给你一个二叉树的根节点root #xff0c;按任意顺序#xff0c;返回所有从根节点到叶子节点的路径。
题目分析
其实从根节点往下走#xff0c… 目录 257. 二叉树的所有路径题目描述题目分析cpp代码 112. 路径总和题目描述题目分析cpp代码 257. 二叉树的所有路径
题目描述
给你一个二叉树的根节点root 按任意顺序返回所有从根节点到叶子节点的路径。
题目分析
其实从根节点往下走遍历的思路就如下图所示。我们先走到叶子节点这是一条路径然后再往上回溯如果回溯到的上层节点有右孩子那么就再按照右边的路径往下走另一条路径。
递归传入参数及返回值
void traversal(TreeNode* cur, vectorint path, vectorstring result)cur是当前节点path用来记录当前路径result是最终返回的结果。
递归终止条件 当我们遍历到叶子节点时就要把当前路径path加入result了。
if(cur-left NULL cur-right NULL) {// 如果当前节点是叶子节点也就是左右孩子都为空// 也就是说已经遍历了一条根节点到叶子节点的路径// 我们要把这条路径放进result中string sPath;for(int i 0; i path.size() - 1; i){sPath to_string(path[i]);sPath -;}sPath to_string(path[path.size() - 1]);result.push_back(sPath);return;}单层递归逻辑 我们进行的是一个前序遍历但是需要注意的是当前节点的处理要在递归终止条件之前进行
path.push_back(cur-val); // 先将当前节点放进当前path中再判断结束条件这是因为所有节点包括叶子节点都要加入path如果先判断终止再处理当前节点则会漏掉叶子节点。
在进行左右孩子的遍历时我们要注意判断节点是否为空
if(cur-left) {traversal(cur-left, path, result);path.pop_back(); // 回溯}if(cur-right) {traversal(cur-right, path, result);path.pop_back(); // 回溯}cpp代码
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:void traversal(TreeNode* cur, vectorint path, vectorstring result){path.push_back(cur-val); // 先将当前节点放进当前path中再判断结束条件if(cur-left NULL cur-right NULL) {// 如果当前节点是叶子节点也就是左右孩子都为空// 也就是说已经遍历了一条根节点到叶子节点的路径// 我们要把这条路径放进result中string sPath;for(int i 0; i path.size() - 1; i){sPath to_string(path[i]);sPath -;}sPath to_string(path[path.size() - 1]);result.push_back(sPath);return;}if(cur-left) {traversal(cur-left, path, result);path.pop_back(); // 回溯}if(cur-right) {traversal(cur-right, path, result);path.pop_back(); // 回溯}}vectorstring binaryTreePaths(TreeNode* root) {vectorint path;vectorstring result;if(root NULL) return result;traversal(root, path, result);return result;}
};112. 路径总和
题目描述
给你二叉树的根节点root和一个表示目标和的整数targetSum。判断该树中是否存在根节点到叶子节点的路径这条路径上所有节点值相加等于目标和targetSum。如果存在返回true否则返回false。
题目分析
其实这题跟上题是一样的只不过这里多了一个targetSum的判断。
cpp代码
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:void traversal(TreeNode* cur, vectorint path, vectorint sum){path.push_back(cur-val);if(cur-left NULL cur-right NULL) {cout 当前路径: ;for(int p : path) {cout p ;}cout endl;sum.push_back(accumulate(path.begin(), path.end(), 0));cout 当前路径总和: accumulate(path.begin(), path.end(), 0) endl;return;}if(cur-left) {traversal(cur-left, path, sum);path.pop_back();}if(cur-right) {traversal(cur-right, path, sum);path.pop_back();}}bool hasPathSum(TreeNode* root, int targetSum) {vectorint path;vectorint sum;if(root NULL) return false;traversal(root, path, sum);if(find(sum.begin(), sum.end(), targetSum) sum.end()){return false;}else return true;}
};
