513. 找树左下角的值
给定一个二叉树的 根节点 root，请找出该二叉树的 最底层 最左边 节点的值。
假设二叉树中至少有一个节点。
示例 1：
输入: root = [3,9,20,null,null,15,7]
输出: 24
解释: 在这个二叉树中，有两个左叶子，分别是 9 和 15，所以返回 24
class Solution {
public:
int findBottomLeftValue(TreeNode* root) {
int result = root->val;
queue<TreeNode*> qt;
qt.push(root);
while (!qt.empty()) {
int size = qt.size();
TreeNode* node = qt.front();
for (int i=0; i<size;i++) {
TreeNode* node = qt.front();
qt.pop();
//关键点
if (i == 0) {
result = node->val;
}
if (node->left) qt.push(node->left);
if (node->right) qt.push(node->right);
}
}
return result;
}
};
注意点：
层次遍历的变种
112. 路径总和
给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。
叶子节点 是指没有子节点的节点。
示例 1：
输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
输出：true
解释：等于目标和的根节点到叶节点路径如上图所示。
class Solution {
public:
bool judgePathSum(TreeNode* root, vector<int>& path, int targetSum) {
bool leftResult = false;
bool rightResult = false;
if (root->left == nullptr && root->right == nullptr) {
int sum = accumulate(path.begin(), path.end(), 0);
if (sum == targetSum) {
//cout << "lll" << endl;
return true;
}
return false;
}
if (root->left) {
path.push_back(root->left->val);
leftResult = judgePathSum(root->left,path,targetSum);
path.pop_back();
}
if (root->right) {
path.push_back(root->right->val);
rightResult = judgePathSum(root->right,path,targetSum);
path.pop_back();
}
bool jj = leftResult || rightResult;
//cout << root->right->val << leftResult << ":" << rightResult << ":" << jj << endl;
return leftResult || rightResult;
}
bool hasPathSum(TreeNode* root, int targetSum) {
vector<int> path;
if (root == nullptr) return false;
path.push_back(root->val);
return judgePathSum(root, path, targetSum);
}
};
注意点：
1.accumulate函数用法、vector所有元素求和可用accumulate函数
2.还是用回溯法。因为跟二叉树的路径遍历有关。一般二叉树求某种路径或者路径上求和，都用回溯法
113. 路径总和 II
给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
叶子节点 是指没有子节点的节点。
example：
输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
输出：[[5,4,11,2],[5,8,4,5]]
class Solution {
public:
void getPathSum(TreeNode* root, vector<int>& path, vector<vector<int>>& result, int targetSum) {
if (root->left == nullptr && root->right == nullptr) {
int sum = accumulate(path.begin(), path.end(), 0);
if (sum == targetSum) {
result.emplace_back(path);
}
return ;
}
if (root->left) {
path.push_back(root->left->val);
getPathSum(root->left,path,result,targetSum);
path.pop_back();
}
if (root->right) {
path.push_back(root->right->val);
getPathSum(root->right,path,result,targetSum);
path.pop_back();
}
return;
}
vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
vector<int> path;
vector<vector<int>> result;
if (root == nullptr) return result;
path.push_back(root->val);
getPathSum(root, path, result, targetSum);
return result;
}
};
注意点：
1.accumulate函数用法、vector所有元素求和可用accumulate函数
2.还是用回溯法。因为跟二叉树的路径遍历有关。一般二叉树求某种路径或者路径上求和，都用回溯法
106.从中序与后序遍历序列构造二叉树，105.从前序与中序遍历序列构造二叉树
没时间 & 看得烦，先跳过
