- 0513.找树左下角的值
- 0112.路径总和
【0513.找树左下角的值】
-
一遍ac
class Solution { public: int findBottomLeftValue(TreeNode* root) { int result = root->val; queue<TreeNode*> que; que.push(root); while(!que.empty()) { int size = que.size(); TreeNode* node1 = que.front(); result = node1->val; for (int i = 0; i < size; i++) { TreeNode* node = que.front(); que.pop(); if (node->left) que.push(node->left); if (node->right) que.push(node->right); } } return result; } };- 很容易想到 用层次遍历的迭代法比较简单
- 关于这点思考了很久----在层次遍历基础代码的基础上 如何实现“最后一层的最左边结点” ----- 其实可以转换为“最后一层的第一个节点”----注意不一定要求是左子树的 只要是第一个就可以满足是最左边的结点
-
递归 还是不太熟 这里粘贴了卡哥代码思路 下次再看看
-
咋眼一看，这道题目用递归的话就就一直向左遍历，最后一个就是答案呗？
没有这么简单，一直向左遍历到最后一个，它未必是最后一行啊。
我们来分析一下题目：在树的最后一行找到最左边的值。
首先要是最后一行，然后是最左边的值。
如果使用递归法，如何判断是最后一行呢，其实就是深度最大的叶子节点一定是最后一行。
如果对二叉树深度和高度还有点疑惑的话，请看：110.平衡二叉树。
所以要找深度最大的叶子节点。
那么如果找最左边的呢？可以使用前序遍历（当然中序，后序都可以，因为本题没有 中间节点的处理逻辑，只要左优先就行），保证优先左边搜索，然后记录深度最大的叶子节点，此时就是树的最后一行最左边的值。
递归三部曲：
- 确定递归函数的参数和返回值
参数必须有要遍历的树的根节点，还有就是一个int型的变量用来记录最长深度。 这里就不需要返回值了，所以递归函数的返回类型为void。
本题还需要类里的两个全局变量，maxLen用来记录最大深度，result记录最大深度最左节点的数值。
代码如下：
int maxDepth = INT_MIN; // 全局变量 记录最大深度 int result; // 全局变量 最大深度最左节点的数值 void traversal(TreeNode* root, int depth)- 确定终止条件
当遇到叶子节点的时候，就需要统计一下最大的深度了，所以需要遇到叶子节点来更新最大深度。
代码如下：
if (root->left == NULL && root->right == NULL) { if (depth > maxDepth) { maxDepth = depth; // 更新最大深度 result = root->val; // 最大深度最左面的数值 } return; }- 确定单层递归的逻辑
在找最大深度的时候，递归的过程中依然要使用回溯，代码如下：
// 中 if (root->left) { // 左 depth++; // 深度加一 traversal(root->left, depth); depth--; // 回溯，深度减一 } if (root->right) { // 右 depth++; // 深度加一 traversal(root->right, depth); depth--; // 回溯，深度减一 } return;完整代码如下：
class Solution { public: int maxDepth = INT_MIN; int result; void traversal(TreeNode* root, int depth) { if (root->left == NULL && root->right == NULL) { if (depth > maxDepth) { maxDepth = depth; result = root->val; } return; } if (root->left) { depth++; traversal(root->left, depth); depth--; // 回溯 } if (root->right) { depth++; traversal(root->right, depth); depth--; // 回溯 } return; } int findBottomLeftValue(TreeNode* root) { traversal(root, 0); return result; } };当然回溯的地方可以精简，精简代码如下：
class Solution { public: int maxDepth = INT_MIN; int result; void traversal(TreeNode* root, int depth) { if (root->left == NULL && root->right == NULL) { if (depth > maxDepth) { maxDepth = depth; result = root->val; } return; } if (root->left) { traversal(root->left, depth + 1); // 隐藏着回溯 } if (root->right) { traversal(root->right, depth + 1); // 隐藏着回溯 } return; } int findBottomLeftValue(TreeNode* root) { traversal(root, 0); return result; } };如果对回溯部分精简的代码 不理解的话，可以看这篇257. 二叉树的所有路径
-
本题涉及如下几点：
- 递归求深度的写法，我们在110.平衡二叉树中详细的分析了深度应该怎么求，高度应该怎么求。
- 递归中其实隐藏了回溯，在257. 二叉树的所有路径中讲解了究竟哪里使用了回溯，哪里隐藏了回溯。
-
【0112.路径总和】
[0112.路径总和]
-
迭代和递归都没思路 其实是有思路 但相比于答案来说比较复杂 --- 之前做过输出二叉树所有路径之和 那么在那道题的基础上 求出所有路径的各自长度 然后一一和题目的targertSum比较 但是比答案要麻烦很多 先看迭代答案吧
-
递归法（赋值粘贴标准答案 介绍的很详细）
可以使用深度优先遍历的方式（本题前中后序都可以，无所谓，因为中节点也没有处理逻辑）来遍历二叉树
- 确定递归函数的参数和返回类型
参数：需要二叉树的根节点，还需要一个计数器，这个计数器用来计算二叉树的一条边之和是否正好是目标和，计数器为int型。
再来看返回值，递归函数什么时候需要返回值？什么时候不需要返回值？这里总结如下三点：
- 如果需要搜索整棵二叉树且不用处理递归返回值，递归函数就不要返回值。（这种情况就是本文下半部分介绍的113.路径总和ii）
- 如果需要搜索整棵二叉树且需要处理递归返回值，递归函数就需要返回值。 （这种情况我们在236. 二叉树的最近公共祖先中介绍）
- 如果要搜索其中一条符合条件的路径，那么递归一定需要返回值，因为遇到符合条件的路径了就要及时返回。（本题的情况）
而本题我们要找一条符合条件的路径，所以递归函数需要返回值，及时返回，那么返回类型是什么呢？
由题可知，遍历的路线，并不要遍历整棵树，所以递归函数需要返回值，可以用bool类型表示。
所以代码如下：
bool traversal(treenode* cur, int count) // 注意函数的返回类型- 确定终止条件
首先计数器如何统计这一条路径的和呢？
不要去累加然后判断是否等于目标和，那么代码比较麻烦，可以用递减，让计数器count初始为目标和，然后每次减去遍历路径节点上的数值。
如果最后count == 0，同时到了叶子节点的话，说明找到了目标和。
如果遍历到了叶子节点，count不为0，就是没找到。
递归终止条件代码如下：
if (!cur->left && !cur->right && count == 0) return true; // 遇到叶子节点，并且计数为0 if (!cur->left && !cur->right) return false; // 遇到叶子节点而没有找到合适的边，直接返回- 确定单层递归的逻辑
因为终止条件是判断叶子节点，所以递归的过程中就不要让空节点进入递归了。
递归函数是有返回值的，如果递归函数返回true，说明找到了合适的路径，应该立刻返回。
代码如下：
if (cur->left) { // 左 （空节点不遍历） // 遇到叶子节点返回true，则直接返回true if (traversal(cur->left, count - cur->left->val)) return true; // 注意这里有回溯的逻辑 } if (cur->right) { // 右 （空节点不遍历） // 遇到叶子节点返回true，则直接返回true if (traversal(cur->right, count - cur->right->val)) return true; // 注意这里有回溯的逻辑 } return false;以上代码中是包含着回溯的，没有回溯，如何后撤重新找另一条路径呢。
回溯隐藏在
traversal(cur->left, count - cur->left->val)这里， 因为把count - cur->left->val直接作为参数传进去，函数结束，count的数值没有改变。为了把回溯的过程体现出来，可以改为如下代码：
if (cur->left) { // 左 count -= cur->left->val; // 递归，处理节点; if (traversal(cur->left, count)) return true; count += cur->left->val; // 回溯，撤销处理结果 } if (cur->right) { // 右 count -= cur->right->val; if (traversal(cur->right, count)) return true; count += cur->right->val; } return false;整体代码如下：
class Solution { private: bool traversal(TreeNode* cur, int count) { if (!cur->left && !cur->right && count == 0) return true; // 遇到叶子节点，并且计数为0 if (!cur->left && !cur->right) return false; // 遇到叶子节点直接返回 if (cur->left) { // 左 count -= cur->left->val; // 递归，处理节点; if (traversal(cur->left, count)) return true; count += cur->left->val; // 回溯，撤销处理结果 } if (cur->right) { // 右 count -= cur->right->val; // 递归，处理节点; if (traversal(cur->right, count)) return true; count += cur->right->val; // 回溯，撤销处理结果 } return false; } public: bool hasPathSum(TreeNode* root, int sum) { if (root == NULL) return false; return traversal(root, sum - root->val); } };以上代码精简之后如下：
class solution { public: bool hasPathSum(TreeNode* root, int sum) { if (root == null) return false; if (!root->left && !root->right && sum == root->val) { return true; } return haspathsum(root->left, sum - root->val) || haspathsum(root->right, sum - root->val); } };是不是发现精简之后的代码，已经完全看不出分析的过程了，所以我们要把题目分析清楚之后，在追求代码精简。 这一点我已经强调很多次了！
-
迭代法
/** * 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: bool hasPathSum(TreeNode* root, int targetSum) { stack <pair<TreeNode*, int>> st; if (root != NULL) st.push(pair<TreeNode*, int>(root, root->val)); while (!st.empty()) { pair<TreeNode*, int> node = st.top(); st.pop(); if (!node.first->left && !node.first->right && node.second == targetSum) 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; } };stack <pair<TreeNode*, int>> st;的定义和使用- return true的条件
[0123.路径总和II]
- 迭代法---再看看