Day16 二叉树part4
找树左下角的值
513.找树左下角的值
力扣题目链接(opens new window)
给定一个二叉树，在树的最后一行找到最左边的值
递归法，前序遍历
/*** 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:// 需要两个global变量，保存最大深度和最左的值int depth = INT_MIN;int result;void traversal(TreeNode* node, int dep){//递归终止if (node->left == NULL && node->right == NULL){if (dep > depth){depth = dep;result = node->val;}return;} if(node->left) traversal(node->left, dep+1); //单层if(node->right) traversal(node->right, dep+1);return; //返回}int findBottomLeftValue(TreeNode* root) {traversal(root, 0);return result;}
};
路径总和
112. 路径总和
力扣题目链接(opens new window)
给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。
说明: 叶子节点是指没有子节点的节点
递归函数什么时候需要返回值？什么时候不需要返回值？这里总结如下三点：
- 如果需要搜索整棵二叉树且不用处理递归返回值，递归函数就不要返回值。（这种情况就是本文下半部分介绍的113.路径总和ii）
- 如果需要搜索整棵二叉树且需要处理递归返回值，递归函数就需要返回值。 （这种情况我们在236. 二叉树的最近公共祖先 (opens new window)中介绍）
- 如果要搜索其中一条符合条件的路径，那么递归一定需要返回值，因为遇到符合条件的路径了就要及时返回。（本题的情况）
/*** 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 traversal(TreeNode* cur, int count) { // count 从目标开始往下减// 终止条件if (!cur->left && !cur->right && count == 0 ) return true; // 通过此逻辑，所以说要传的是下一个节点以及减去下一个节点后的值if (!cur->left && !cur->right) return false;// 单层if (cur->left){if (traversal(cur->left, count - cur->left->val)) return true;}if (cur->right){if (traversal(cur->right, count - cur->right->val)) return true;}//返回return false;}bool hasPathSum(TreeNode* root, int targetSum) {if (root == NULL) return false;return traversal(root, targetSum - root->val);}
};//精简
class Solution {
public:bool hasPathSum(TreeNode* root, int sum) {if (!root) 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);}
};
113. 路径总和ii
力扣题目链接(opens new window)
给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。
说明: 叶子节点是指没有子节点的节点。
路径总和ii要遍历整个树，找到所有路径，所以递归函数不要返回值！
/*** 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 {
private:vector<vector<int>> result;vector<int> path;void traversal(TreeNode* node, int count){if (!node->left && !node->right && count == 0) {result.push_back(path);return;}if (!node->left && !node->right) return;if (node->left){path.push_back(node->left->val);traversal(node->left, count - node->left->val);path.pop_back();}if (node->right){path.push_back(node->right->val);traversal(node->right, count - node->right->val);path.pop_back();}return;}public:vector<vector<int>> pathSum(TreeNode* root, int targetSum) {if (root == NULL) return result;path.push_back(root->val); // 把根节点放进路径traversal(root, targetSum - root->val);return result;}
};