今日刷题重点—求树左下角值+二叉树满足条件的路径之和.
513. 找树左下角的值
给定一个二叉树的 根节点 root，请找出该二叉树的 最底层 最左边 节点的值。
假设二叉树中至少有一个节点。
示例 1:
输入: root = [2,1,3] 输出: 1
示例 2:
输入: [1,2,3,4,null,5,6,null,null,7] 输出: 7
思路分析
这道题用层次遍历最简单了,不过我们先试下递归法.
我们分析以下题目要求:寻找最底层最左边的节点.
我们很容易想到一直向左递归,最后那个节点不就是最左边的那个节点吗? 事实上不是的.因为不仅要求最左边还要求了最底层.
方法一:递归
使用递归法,如何判断是最后一行呢?其实就是我们进行递归时深度最大的叶子节点一定是最后一行. 由于我们寻找的是最左边,所以我们可以先进行左递归,之后更新maxLeftVal 的值.之后再右递归(防止前面那个不是最后一层).我们结束条件是叶子节点,so 可以使用先序遍历.
递归三部曲:
参数和返回值:参数为要递归的节点以及到当前节点的深度.由于递归的是整个树,所以不需要返回值.
结束条件:当递归节点是叶子节点时,先进行逻辑处理,之后进行结束本层递归.
单层递归逻辑:先向左递归,再向右递归(中间暗含着回溯),每次传入的深度+
参考代码1
int maxLeft = INT_MIN;//最大深度 int maxLeftVal = 0; //最大深度对应的叶子节点的值. void traversal(TreeNode* node,int leftLen) { //参数为需要遍历的树的根节点, leftLen:从根节点到当前node的高度. if(!node->left&&!node->right) { //如果当前节点为叶子节点 //更新 if(leftLen>maxLeft) { maxLeft = leftLen; maxLeftVal = node->val; } return; } //向左递归 if(node->left) { traversal(node->left,leftLen+1);//中间暗含着回溯.. } if(node->right) { //向右递归是为了防止,目标节点不在左子树上,而是在右子树上.. traversal(node->right,leftLen+1); } } //方法一:递归. int findBottomLeftValue(TreeNode* root) { traversal(root,1);// return maxLeftVal; }
方法二:迭代法(层次遍历)
只需要在每层遍历时保存第一个节点值即可,最后返回的一定是最后一层且最左边的节点的值.
参考代码2
//方法二:迭代法(层次遍历) int findBottomLeftValue(TreeNode* root) { queue<TreeNode*> Q; Q.push(root); int res; while(!Q.empty()){ int size = Q.size(); for(int i = 0;i < size;i++){ TreeNode* node = Q.front(); Q.pop(); if(node->left){ Q.push(node->left); } if(node->right){ Q.push(node->right); } if(!i){ res = node->val; } } } return res; }
112. 路径总和
给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。
叶子节点 是指没有子节点的节点。
示例 1：
输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22 输出：true
解释：等于目标和的根节点到叶节点路径如上图所示。
示例 2：
输入：root = [1,2,3], targetSum = 5 输出：false
解释：树中存在两条根节点到叶子节点的路径：
(1 --> 2): 和为 3
(1 --> 3): 和为 4
不存在 sum = 5 的根节点到叶子节点的路径。
示例 3：
输入：root = [], targetSum = 0 输出：false
解释：由于树是空的，所以不存在根节点到叶子节点的路径。
方法一:递归
我们这个题的目的是:遍历从根节点到叶子节点的的路径看看总和是不是目标和
递归三要素:
参数和返回值:参数为需要遍历的树的根节点,遍历到当前节点的和值以及目标值; 因为要搜索其中一条符合条件的路径，那么递归一定需要返回值，因为遇到符合条件的路径了就要及时返回。 返回值为当前路径以及节点是否满足之和为targetSum
递归结束条件:如果是叶子节点时就需要判断curSum和targetSum是否相等,同时结束向下的递归.
单层递归的逻辑:先向左递归,再向右递归,最后返回两个递归后的共同结果(之间是 || 的关系)
参考代码1
// 慢慢的自己对于一些题也有了自己的一些思路...学习本身就是一个孰能生巧的过程啊.. bool traversal(TreeNode* node,int curSum,int targetSum) { //targetSum(这个可以使用一个全局变量保存,这样就不用再进行参数传递了) //返回值为:当前节点下是否存在该路径以及叶子节点. if(!node->left&&!node->right) { //结束条件为当时叶子节点,然后判断是否成立,如果是返回true.. if(curSum==targetSum) { return true; } else { return false; } } //向左递归 bool flag1 = false; if(node->left) { flag1 = traversal(node->left,curSum+node->left->val,targetSum); } //向右递归. bool flag2 = false; if(node->right) { flag2 = traversal(node->right,curSum+node->right->val,targetSum); } //返回 flag1||falg2; return flag1 || flag2; } bool hasPathSum(TreeNode* root, int targetSum) { if(root==NULL) { return false; } bool flag = traversal(root,root->val,targetSum); return flag; }
参考代码2(大佬的递归做法)
在参数传递时我们也可以传入当当前节点为止 需要的剩余的节点的和值. 这样相比上一个代码就少一个参数传递了.
//大佬的递归做法(使用两个参数.) //cnt:表示到当前节点后还需要增加的节点的值的大小. bool traversal(TreeNode* node,int cnt) { //返回值为:当前节点下是否存在该路径以及叶子节点. if(!node->left&&!node->right) { //结束条件为当时叶子节点,然后判断是否成立,如果是返回true.. if(!cnt) { return true; } else { return false; } } //向左递归 bool flag1 = false; if(node->left) { flag1 = traversal(node->left,cnt-node->left->val); } //向右递归. bool flag2 = false; if(node->right) { flag2 = traversal(node->right,cnt-node->right->val); } //返回 flag1||falg2; return flag1 || flag2; } bool hasPathSum(TreeNode* root, int targetSum) { if(root==NULL) { return false; } return traversal(root,targetSum-root->val); }
方法二:迭代法(栈模拟)
目前还看不懂~~~ 呜呜呜
参考代码3
bool haspathsum(treenode* root, int sum) { if (root == null) return false; // 此时栈里要放的是pair<节点指针，路径数值> stack<pair<treenode*, int>> st; st.push(pair<treenode*, int>(root, root->val)); while (!st.empty()) { pair<treenode*, int> node = st.top(); st.pop(); // 如果该节点是叶子节点了，同时该节点的路径数值等于sum，那么就返回true if (!node.first->left && !node.first->right && sum == node.second) return true; // 右节点，压进去一个节点的时候，将该节点的路径数值也记录下来 if (node.first->right) { st.push(pair<treenode*, int>(node.first->right, node.second + node.first->right->val)); } // 左节点，压进去一个节点的时候，将该节点的路径数值也记录下来 if (node.first->left) { st.push(pair<treenode*, int>(node.first->left, node.second + node.first->left->val)); } } return false; }
113. 路径总和 II
给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
叶子节点 是指没有子节点的节点。
示例 1：
输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22 输出：[[5,4,11,2],[5,8,4,5]]
示例 2：
输入：root = [1,2,3], targetSum = 5 输出：[]
思路分析
这个题和 上一个题 很相似,不同之处在于需要保存下路径,所以我们可以定义vector<vector<int>> res; 和vector<int> temp;一个保存结果,一个保存路径.
其他的处理和上一个题方法类似,就是注意递归前后需要进行回溯. 而且我们寻找的是所有满足的路径,遍历的是整棵树,结果还保存在全局变量里面,所以递归就不需要返回值了.
参考代码
vector<vector<int>> res; vector<int> temp; void traversal(TreeNode* node,int curSum,int targetSum) { //遍历整棵树不需要有返回值,参数:要遍历的树的根节点,当根节点为止当前的curSum以及目标值 if(!node->left&&!node->right) { //当遇到叶子节点时开始判断是否找到该路径 if(curSum==targetSum){ res.push_back(temp); } } //向左递归 if(node->left){ temp.push_back(node->left->val);//将节点放入临时的temp. traversal(node->left,curSum+node->left->val,targetSum); temp.pop_back();//回溯弹出该节点. } //向右递归 if(node->right){ temp.push_back(node->right->val); traversal(node->right,curSum+node->right->val,targetSum); temp.pop_back();//回溯弹出该节点. } } vector<vector<int>> pathSum(TreeNode* root, int targetSum) { if(root==NULL) { return {}; } res.push_back(root->val); traversal(root,root->val,targetSum); return res; }
备注:
递归函数什么时候需要返回值？什么时候不需要返回值？ 这里根据如下三点：
如果需要搜索整颗二叉树且不用处理递归返回值，递归函数就不要返回值。（这种情况就是介绍的113.路径总和ii）
如果需要搜索整颗二叉树且需要处理递归返回值，递归函数就需要返回值。 （这种情况我们在236. 二叉树的最近公共祖先 (opens new window)中介绍）
如果要搜索其中一条符合条件的路径，那么递归一定需要返回值，因为遇到符合条件的路径了就要及时返回。（112.路径总和）
今天自己完成了LeetCode100题(10.18—12.10),之后继续哇!!!
