路径问题涉及回溯回溯一般和递归捆绑在一起 一般递归函数为void型参数有结点，结果类型的一个遍历变量，（如果需要存放路径）定义一个容器存放函数体首先第一步把结点值放入遍历变量中，然后判断是否是叶结点，是则进行相应处理，并且return；如果不是则递归（遍历变量还是path，函数中处理），并且回溯； 迭代法中的回溯一般使用两个栈来模拟 一个栈用来遍历二叉树；一个栈用来模拟递归用来存放和当前结点对应的已经遍历的路径；同时pop更新，同时压入栈（结点，当前路径（注意会改变变量的情况，设置tmp变量）），如果叶结点则处理。

257. 二叉树的所有路径

给定一个二叉树，返回所有从根节点到叶子节点的路径。 说明: 叶子节点是指没有子节点的节点。 示例: 输入: 1 / \ 2 3 \ 5 输出: ["1->2->5", "1->3"] 解释: 所有根节点到叶子节点的路径为: 1->2->5, 1->3 通过次数79,782提交次数120,766

递归法思路：用前序遍历，但是每次遍历都需要回溯

vector<string> binaryTreePaths(TreeNode* root) { vector<string> result; vector<int> path; if(root==NULL) return result; traversal(root,path,result); return result; } //求的路径 从上到下遍历 用前序遍历 返回值为空 //参数分别为当前路径 总结果 当前结点 //定义成引用 void traversal(TreeNode* cur,vector<int>& path,vector<string>& result){ path.push_back(cur->val); //返回条件 if(cur->left==NULL&&cur->right==NULL){ string tmp; for(int i=0;i<path.size()-1;i++){ tmp+=to_string(path[i]); tmp+="->"; } tmp+=to_string(path[path.size()-1]); result.push_back(tmp); return;//不用返回值，直接return 结果都存好了 } if(cur->left){ traversal(cur->left,path,result); path.pop_back();//递归和回溯一定要绑定在一起 } if(cur->right){ traversal(cur->right,path,result); path.pop_back();//递归和回溯一定要绑定在一起 } }

迭代法思路：两个栈来做

vector<string> binaryTreePaths(TreeNode* root) { vector<string> result;//存放结果 stack<TreeNode*> treest;//遍历树的结点 stack<string> pathst;//遍历路径的结点 if(root==NULL) return result; treest.push(root); pathst.push(to_string(root->val)); while(!treest.empty()){ TreeNode* cur=treest.top(); treest.pop(); string path=pathst.top();//获取当前结点的已经遍历的路径 pathst.pop(); if(cur->left==NULL&&cur->right==NULL) result.push_back(path); if(cur->right) { //前序先右后左 treest.push(cur->right); pathst.push(path+"->"+to_string(cur->right->val)); } if(cur->left) { //前序先右后左 treest.push(cur->left); pathst.push(path+"->"+to_string(cur->left->val)); } } return result; }

113. 路径总和 II

给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。 说明: 叶子节点是指没有子节点的节点。 示例: 给定如下二叉树，以及目标和 sum = 22， 5 / \ 4 8 / / \ 11 13 4 / \ / \ 7 2 5 1 返回: [ [5,4,11,2], [5,8,4,5] ] /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution1 {//迭代 public: vector<vector<int>> pathSum(TreeNode* root, int sum) { vector<vector<int>> res; stack<TreeNode*> stmp; stack<vector<int>> vtmp;//和栈同步跟新，记录当前遍历值 if(root==NULL) return res; stmp.push(root); vector<int> tmp; tmp.push_back(root->val); vtmp.push(tmp); while(!stmp.empty()){ TreeNode* cur=stmp.top(); stmp.pop(); vector<int> tmp=vtmp.top(); vtmp.pop(); if(cur->left==NULL&&cur->right==NULL){ int sum1= accumulate(tmp.begin(),tmp.end(),0); if(sum1==sum) res.push_back(tmp); } if(cur->right) { stmp.push(cur->right); vector<int> vi=tmp; vi.push_back(cur->right->val); vtmp.push(vi); } if(cur->left){ stmp.push(cur->left); vector<int> vi=tmp; vi.push_back(cur->left->val); vtmp.push(vi); } } return res; } }; class Solution {//递归 public: vector<vector<int>> pathSum(TreeNode* root, int sum) { vector<vector<int>> res; vector<int> path; if(root==NULL) return res; getPath(root,path,res,sum); return res; } void getPath(TreeNode* cur, vector<int>& path,vector<vector<int>>& res,int sum){ path.push_back(cur->val); if(cur->left==NULL&&cur->right==NULL){ int sum1=accumulate(path.begin(),path.end(),0); if(sum==sum1) res.push_back(path); return;//不用返回值，直接return 结果都存好了 } if(cur->right) { getPath(cur->right,path,res,sum); path.pop_back(); } if(cur->left){ getPath(cur->left,path,res,sum); path.pop_back(); } } };

112. 路径总和

给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。 说明: 叶子节点是指没有子节点的节点。 示例: 给定如下二叉树，以及目标和 sum = 22， 5 / \ 4 8 / / \ 11 13 4 / \ \ 7 2 1 返回 true, 因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2。 class Solution { public: bool hasPathSum(TreeNode* root, int sum) { vector<int> path; if(root==NULL) return false; bool flag=false; getPath(root,sum,path,flag); return flag; } void getPath(TreeNode* cur,int sum,vector<int>&path,bool& flag){ path.push_back(cur->val); if(cur->left==NULL&&cur->right==NULL){ int sum1=accumulate(path.begin(),path.end(),0); cout<<sum1<<endl; if(sum1==sum) flag=true; } if(cur->left){ getPath(cur->left,sum,path,flag); path.pop_back(); } if(cur->right){ getPath(cur->right,sum,path,flag); path.pop_back(); //递归就不用记录当前的遍历路径 只需要回溯 } } };

129. 求根到叶子节点数字之和

129. 求根到叶子节点数字之和 给定一个二叉树，它的每个结点都存放一个 0-9 的数字，每条从根到叶子节点的路径都代表一个数字。 例如，从根到叶子节点路径 1->2->3 代表数字 123。 计算从根到叶子节点生成的所有数字之和。 说明: 叶子节点是指没有子节点的节点。 示例 1: 输入: [1,2,3] 1 / \ 2 3 输出: 25 解释: 从根到叶子节点路径 1->2 代表数字 12. 从根到叶子节点路径 1->3 代表数字 13. 因此，数字总和 = 12 + 13 = 25. 示例 2: 输入: [4,9,0,5,1] 4 / \ 9 0 / \ 5 1 输出: 1026 解释: 从根到叶子节点路径 4->9->5 代表数字 495. 从根到叶子节点路径 4->9->1 代表数字 491. 从根到叶子节点路径 4->0 代表数字 40. 因此，数字总和 = 495 + 491 + 40 = 1026. 通过次数41,309提交次数63,792

递归法

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution1 {//递归法 public: int sumNumbers(TreeNode* root) { int res=0; if(root==NULL) return res; string path; getPath(root,path,res); return res; } void getPath(TreeNode* cur,string& path,int& res){ path+=to_string(cur->val); if(cur->left==NULL&&cur->right==NULL){ int tmp=stoi(path); cout<<tmp<<endl; res+=tmp; return;//此处return很重要 } if(cur->left){ getPath(cur->left, path,res); path.pop_back(); } if(cur->right){ getPath(cur->right,path,res); path.pop_back(); } } };

迭代法

class Solution {//迭代法 public: int sumNumbers(TreeNode* root) { int res=0; if(root==NULL) return res; string path;//记录当前路径 stack<string> st;//栈用来记录当前上面的路径，用来模拟递归 stack<TreeNode*> ts;//用来遍历二叉树 path+=to_string(root->val); st.push(to_string(root->val)); ts.push(root); while(!ts.empty()){ TreeNode* cur=ts.top(); ts.pop(); string path=st.top(); st.pop(); if(cur->left==NULL&&cur->right==NULL){ int tmp=stoi(path); res+=tmp; } if(cur->left){ ts.push(cur->left); st.push(path+to_string(cur->left->val)); } if(cur->right){ ts.push(cur->right); st.push(path+to_string(cur->right->val)); } } return res; } };

988. 从叶结点开始的最小字符串

988. 从叶结点开始的最小字符串 给定一颗根结点为 root 的二叉树，树中的每一个结点都有一个从 0 到 25 的值，分别代表字母 'a' 到 'z'：值 0 代表 'a'，值 1 代表 'b'，依此类推。 找出按字典序最小的字符串，该字符串从这棵树的一个叶结点开始，到根结点结束。 （小贴士：字符串中任何较短的前缀在字典序上都是较小的：例如，在字典序上 "ab" 比 "aba" 要小。叶结点是指没有子结点的结点。） 示例 1： 输入：[0,1,2,3,4,3,4] 输出："dba" 示例 2： 输入：[25,1,3,1,3,0,2] 输出："adz" 示例 3： 输入：[2,2,1,null,1,0,null,0] 输出："abc" 提示： 给定树的结点数介于 1 和 8500 之间。 树中的每个结点都有一个介于 0 和 25 之间的值。 /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution1 { public: string smallestFromLeaf(TreeNode* root) { string path; string res; if(root==NULL) return res; getPath(root,path,res); return res; } void getPath(TreeNode* cur,string& path,string& res){ path+=char(cur->val+97);//转换为char cout<<char(cur->val+97)<<endl; if(cur->left==NULL&&cur->right==NULL){ string tmp=path; reverse(tmp.begin(),tmp.end()); // cout<<"path:"<<path<<endl; if(res.size()==0) res=tmp; res=tmp>res?res:tmp; cout<<res<<endl; } if(cur->left){ getPath(cur->left,path,res); path.pop_back(); } if(cur->right){ getPath(cur->right,path,res); path.pop_back(); } } }; class Solution { public: string smallestFromLeaf(TreeNode* root) { string res; stack<TreeNode*> st; stack<string> sp; if(root==NULL) return res; st.push(root); string tmp(1,(char(root->val+97))); sp.push(tmp); while(!st.empty()){ TreeNode* cur=st.top(); st.pop(); string path=sp.top(); sp.pop(); if(cur->left==NULL&&cur->right==NULL){ string tmp=path; reverse(tmp.begin(),tmp.end()); cout<<"tmp:"<<tmp<<endl; if(res.size()==0) res=tmp; res=tmp>res?res:tmp; cout<<"res:"<<res<<endl; } if(cur->right){ st.push(cur->right); string tmp(1,char(cur->right->val+97)); cout<<"right:"<<tmp<<endl; cout<<"right:"<<path+tmp<<endl; sp.push(path+tmp); } if(cur->left){ st.push(cur->left); string tmp(1,char(cur->left->val+97)); cout<<"left:"<<tmp<<endl; cout<<"left:"<<path+tmp<<endl; sp.push(path+tmp); } } return res; } };

437. 路径总和 III

437. 路径总和 III 给定一个二叉树，它的每个结点都存放着一个整数值。 找出路径和等于给定数值的路径总数。 路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。 二叉树不超过1000个节点，且节点数值范围是 [-1000000,1000000] 的整数。 示例： root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8 10 / \ 5 -3 / \ \ 3 2 11 / \ \ 3 -2 1 返回 3。和等于 8 的路径有: 1. 5 -> 3 2. 5 -> 2 -> 1 3. -3 -> 11 通过次数53,997提交次数96,441

思路；两层遍历，遍历使用迭代和递归皆可

class Solution { public: int pathSum1(TreeNode* root, int sum) {//迭代超时 int res=0; stack<TreeNode*> st; if(root==NULL) return res; st.push(root); while(!st.empty()){ TreeNode* cur=st.top(); st.pop(); vector<int> path; getPath(cur,path,sum,res); if(cur->right) st.push(cur->right); if(cur->left) st.push(cur->left); } return res; } int res=0; int pathSum(TreeNode* root, int sum) {//换成递归卡在了一个有误的数据 if(root==NULL) return res; vector<int> path; cout<<"root:"<<root->val<<endl; getPath(root,path,sum,res); vector<int> pathleft; if(root->left) { getPath(root->left,pathleft,sum,res); cout<<"root->left:"<<root->left->val<<endl;} vector<int> pathright; if(root->right) {getPath(root->right,pathright,sum,res); cout<<"root->right:"<<root->right->val<<endl;} return res; } void getPath(TreeNode* cur,vector<int>& path,int sum,int& res){ path.push_back(cur->val); cout<<"cur:"<<cur->val<<endl; for(auto i:path) cout<<"path:"<<i; cout<<endl; if(accumulate(path.begin(),path.end(),0)==sum){ res++; //此处不能加return 因为当满足条件时继续往下走的时候也会可能还有情况 } if(cur->left){ getPath(cur->left,path,sum,res); path.pop_back(); } if(cur->right){ getPath(cur->right,path,sum,res); path.pop_back(); } } };

404. 左叶子之和

404. 左叶子之和 计算给定二叉树的所有左叶子之和。 示例： 3 / \ 9 20 / \ 15 7 在这个二叉树中，有两个左叶子，分别是 9 和 15，所以返回 24

思路：如何判断是不是左叶结点呢，递归函数设置一个isleft布尔值，当是最后一个结点的时候判断是不是左结点

class Solution { public: int sumOfLeftLeaves(TreeNode* root) { int res=0; if(root==NULL) return res; vector<int> path; bool isleft=false; getLeftLeaves(root,path,res,isleft); return res; } void getLeftLeaves(TreeNode* cur,vector<int>& path,int& res,bool& isleft){ path.push_back(cur->val); if(cur->left==NULL&&cur->right==NULL&&isleft){ res+=cur->val; } if(cur->left){ isleft=true; getLeftLeaves(cur->left,path,res,isleft); path.pop_back(); } if(cur->right){ isleft=false; getLeftLeaves(cur->right,path,res,isleft); path.pop_back(); } } };