今日刷题重点–二叉树的路径以及左/右叶子之和.
257. 二叉树的所有路径
给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。
叶子节点 是指没有子节点的节点。
示例 1：
输入：root = [1,2,3,null,5] 输出：["1->2->5","1->3"]
示例 2：
输入：root = [1] 输出：["1"]
思路分析
这道题要求从根节点到叶子的路径所以需要先序遍历,这样方便父节点指向孩子节点.
因为找的是所有叶子节点的路径,所有递归中必有回溯思想.
示意图如下:
递归三要素:
参数和返回值:参数是要递归的树的根节点,另外需要一个vector<int> path记录递归到当前根节点的路径.还有一个vector<string> res 保存结果集.
由于遍历的是整棵树,所有不需要有返回值.
结束条件:当遇到叶子节点,就把path存入到res中.并结束本层递归
确定单层递归逻辑: 将左子树节点放入path,向左进行递归遍历,遍历完毕之后进行回溯. 之后将右子树节点放入path,向右进行递归遍历,遍历完毕后进行回溯.
运行结果
void traversal(TreeNode* node,vector<int> &path,vector<string> &res){//path:遍历到node时的路径,res:结果集也可以声明成全局变量,这样就可以不用参数传递了. if(node->left==NULL&&node->right==NULL){//当该节点是叶子节点时. string temp = ""; int i; for(i = 0;i < path.size()-1;i++){ temp+=to_string(path[i]); temp+="->"; } temp+=to_string(path[i]); res.push_back(temp);//加入到结果集中 return;//结束 } if(node->left){ path.push_back(node->left->val);//把当前节点的值放入path中 traversal(node->left,path,res); path.pop_back();//递归完成进行回溯(弹出node->left节点)..之后尝试其他路径 (比如node->right) } if(node->right){ path.push_back(node->right->val); traversal(node->right,path,res); path.pop_back();//递归完成进行回溯..之后尝试其他路径 } } //方法一:递归 vector<string> binaryTreePaths(TreeNode* root) { vector<string> res; vector<int> path; if(root==NULL){ return {}; } path.push_back(root->val); traversal(root,path,res); return res; }
404. 左叶子之和
计算给定二叉树的所有左叶子之和。
示例：
3 / \ 9 20 / \ 15 7
在这个二叉树中，有两个左叶子，分别是 9 和 15，所以返回 24
思路分析
注意判断的是左叶子,不是二叉树左侧节点,所以层次遍历这样的思路是不对的.
左叶子:如果左节点不为空，且左节点没有左右孩子，那么这个节点就是左叶子
比如上面这棵树的左叶子节点为0,因为它没有叶子位于左边.
方法1:递归法(菜鸡的做法)
既然是判断左叶子,那么该节点得符合当前节点是叶子节点,并且得满足父节点的左孩子是该节点.
递归三要素:
参数和返回值:参数就是当前节点以及其父节点. 由于存放结果的res是全局变量,所以不需要返回值.
结束条件:当节点是叶子节点时,判断父节点的左节点是否是该节点,然后进行处理.最后进行return,结束递归.
单层递归逻辑:更新父节点,继续向左递归遍历,向右递归遍历.
参考代码1
int res = 0; void traversal(TreeNode* cur,TreeNode* pre){ if(!cur->left && !cur->right){//叶子节点 if(pre->left==cur){ res+=cur->val; } return; } pre = cur; if(cur->left){ traversal(cur->left,pre); } if(cur->right){ traversal(cur->right,pre); } } int sumOfLeftLeaves(TreeNode* root) { if(root==NULL) { //结束条件.. return 0; } traversal(root,root); return res; }
方法2:递归法(大佬的做法)
递归三要素:
参数和返回值:参数为要遍历的树的根节点. 返回值左叶子之和,为int
递归结束条件:当节点为NULL时,返回0,表示左叶子节点为0
单层递归逻辑:先求左子树的左叶子节点之和left,再求右子树的左叶子节点之和,最后再求当前节点是否是左叶子节点如果是则保存其值, 最后的返回值是三部分之和.
参考代码2
//递归 int sumOfLeftLeaves(TreeNode* root) {//每一次都判断当前节点是不是左叶子节点的父节点,如果是进行操作. if(root==NULL) { //结束条件.. return 0; } int leftSum = sumOfLeftLeaves(root->left); int rightSum = sumOfLeftLeaves(root->right); int midSum = 0; if(root->left&&!root->left->left&&!root->left->right) { midSum = root->left->val; } return leftSum+rightSum+midSum; }
方法三:迭代法(层次遍历)
本题迭代法使用前中后序都是可以的，只要把左叶子节点统计出来，就可以了,以下是前序遍历的做法.
参考代码3
//迭代法 int sumOfLeftLeaves(TreeNode* root) { stack<TreeNode*> tab; if(root==NULL) { return 0; } tab.push(root); int res; while(!tab.empty()) { TreeNode* node = tab.top(); tab.pop(); if(node->left&&!node->left->left&&!node->left->right) {//当然这里也可以改成父节点pre,和当前节点的思路. res+=node->left->val; } if(node->right) { tab.push(node->right); } if(node->left) { tab.push(node->left); } } return res; }
