1.树左下角的值 (指的是最后一层的第一个值，而不是左右一层的左叶子节点的值)
- LeetCode链接
给定一个二叉树的 根节点 root，请找出该二叉树的 最底层 最左边 节点的值。
假设二叉树中至少有一个节点。
- 遍历顺序，因为本题要求的是 最后一层最左边的节点，因此只要遍历顺序 左节点在右节点前就行，因此 任何遍历顺序都可以
- 本题中的中节点 不需要处理逻辑，只需要判断是否到了叶子节点，并且判断当前遍历的叶子节点的深度是否是大于maxDepth
class Solution {
public:
int maxDepth = INT_MIN;
int result;
void travel(TreeNode* root, int depth){
if(root->left == NULL && root->right == NULL){
if(depth > maxDepth){
result = root->val;
maxDepth = depth;
}
return ;
}
if(root->left){
travel(root->left, depth+1);
}
if(root->right){
travel(root->right, depth+1);
}
return ;
}
int findBottomLeftValue(TreeNode* root) {
travel(root, 0);
return result;
}
};
2.路径总和i 和 ii
- LeetCode链接1
- LeetCode链接2
路径总和 i
给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。
class Solution {
public:
bool hasPathSum(TreeNode* root, int targetSum) {
if(root==NULL) return false;
// 使用叶子节点判断
if(root->left == NULL && root->right == NULL){ // 判断到达了叶子节点
if(targetSum == root->val) return true;
else return false;
}
// if(root == NULL && targetSum == 0) return true;
// else if(root == NULL && targetSum != 0) return false;
targetSum -= root->val;
bool left_flag = hasPathSum(root->left, targetSum);
bool right_flag = hasPathSum(root->right, targetSum);
return left_flag || right_flag;
}
};
路径总和 ii
给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。文章来源：https://www.toymoban.com/news/detail-443560.html
class Solution {
public:
vector<vector<int>> result;
vector<int> temVec;
void travel(TreeNode* root, int targetSum){
temVec.push_back(root->val);
if(root->left == NULL && root->right == NULL && root->val==targetSum){
result.push_back(temVec);
return ;
}
if(root->left == NULL && root->right == NULL) return ;
// 中
if(root->left){
travel(root->left, targetSum-root->val);
temVec.pop_back();
}
if(root->right){
travel(root->right, targetSum-root->val);
temVec.pop_back();
}
return ;
}
vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
if(root == NULL) return result;
travel(root, targetSum);
return result;
}
};
3.中序和后序遍历构造二叉树
- LeetCode链接文章来源地址https://www.toymoban.com/news/detail-443560.html
class Solution {
public:
TreeNode* travel(vector<int>& inorder, vector<int>& postorder){
if(postorder.size() == 0) return NULL;
// 后序遍历的数组的最后一个元素是 当前的中间节点
int rootValue = postorder[postorder.size() - 1];
TreeNode* root = new TreeNode(rootValue);
// 判断是否是叶子节点
if(postorder.size() == 1) return root;
// 找到中序遍历的切割点
int delimiterIndex;
for(delimiterIndex = 0; delimiterIndex < inorder.size(); delimiterIndex++){
if(inorder[delimiterIndex] == rootValue) break;
}
// 切割中序数组 左闭右开区间
vector<int> leftInorder(inorder.begin(), inorder.begin() + delimiterIndex);
vector<int> rightInorder(inorder.begin()+delimiterIndex+1, inorder.end());
// postorder舍弃末尾元素
postorder.resize(postorder.size()- 1);
// 切割后续数组
vector<int> leftPostorder(postorder.begin(), postorder.begin() +leftInorder.size());
vector<int> rightPostorder(postorder.begin()+leftInorder.size(), postorder.end());
root->left = travel(leftInorder, leftPostorder);
root->right = travel(rightInorder, rightPostorder);
return root;
}
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
if(inorder.size() == 0 || postorder.size() == 0) return NULL;
return travel(inorder, postorder);
}
};
到了这里，关于第18天-代码随想录刷题训练-第六章● 513.找树左下角的值 ● 112. 路径总和 113.路径总和ii ● 106.从中序与后序遍历序列构造二叉树 105.从前序与中序遍历序列构造二叉树的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
