# Day18左下角的值，路径总和，构建二叉树
`By HQWQF 2023/12/30`
## 笔记
***
## 513.找树左下角的值
给定一个二叉树的 **根节点** `root`，请找出该二叉树的 **最底层 最左边** 节点的值。
假设二叉树中至少有一个节点。
**示例 2:**
**输入:** \[1,2,3,4,null,5,6,null,null,7]
**输出:** 7
#### 递归法
我们要找的目标节点有两个要求
1. 最底层，也就是说这个节点的深度是最大的节点之一
2. 最左边，这个节点在深度最大的节点中必须是最左边的
求最大深度我们之前做过，至于最左边，我们可以在递归代码在**确保优先递归左边**，在遍历过程中不断维护一个最大深度，只要最大深度更新就将当前节点保存为目标节点，这样**在更新最大深度后，在所有相同深度的节点中这个节点一点是最左边的**，通过不断更新目标节点，我们最终能得到 **最底层 最左边** 的节点。
#### 递归法代码
```c++
class Solution {
public:
int findBottomLeftValue(TreeNode* root)
{
TreeNode* &targetNode = root;
int maxdeep = 0;
t(root,targetNode,1,maxdeep);
return targetNode->val;
}
void t(TreeNode* node,TreeNode* &targetNode,int deep,int &maxdeep)
{
if(node == nullptr){return;}
if(deep > maxdeep){maxdeep = deep;targetNode = node;}
t(node->left,targetNode,deep + 1,maxdeep);
t(node->right,targetNode,deep + 1,maxdeep);
}
};
```
另外一种写法：
```c++
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;
}
};
```
#### 迭代法
迭代法相对更简单，可以使用层序遍历然后直接读取最后一层的第一个元素。
#### 迭代法代码
```c++
class Solution {
public:
int findBottomLeftValue(TreeNode* root)
{
queue<TreeNode*> que;
if (root != NULL) que.push(root);
vector<vector<int>> result;
while (!que.empty()) {
int size = que.size();
vector<int> vec;
// 这里一定要使用固定大小size，不要使用que.size()，因为que.size是不断变化的
for (int i = 0; i < size; i++) {
TreeNode* node = que.front();
que.pop();
vec.push_back(node->val);
if (node->left) que.push(node->left);
if (node->right) que.push(node->right);
}
result.push_back(vec);
}
return result[result.size()-1][0];
}
};
```
当然也可以在层序遍历中不断更新目标值为每层的第一个元素，遍历结束后我们就能得到结果了
```c++
class Solution {
public:
int findBottomLeftValue(TreeNode* root) {
queue<TreeNode*> que;
if (root != NULL) que.push(root);
int result = 0;
while (!que.empty()) {
int size = que.size();
for (int i = 0; i < size; i++) {
TreeNode* node = que.front();
que.pop();
if (i == 0) result = node->val; // 记录最后一行第一个元素
if (node->left) que.push(node->left);
if (node->right) que.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
**解释：** 等于目标和的根节点到叶节点路径如上图所示。
#### 递归法
**确定返回值**：返回当前节点作为根节点的子树是否有目标路径，只要节点的左右子树有一个有目标路径则该节点子树有目标路径。
**确定参数传递**意义：除了节点变化外，使用一个参数表示根节点到当前节点的父节点的路径总和
**确定终止条件**：遍历到空节点返回false，遍历到叶子节点就判断是否路径总和参数+当前节点是否等于目标值，等于则返回true，反之则返回false。
#### 递归法代码
```c++
class Solution {
public:
bool hasPathSum(TreeNode* root, int targetSum) {
return test(root,targetSum,0);
}
bool test(TreeNode* node,int targetSum,int nowSum)
{
if(node == nullptr){return false;}
if(node->left == nullptr && node->right == nullptr)
{
if(nowSum + node->val ==targetSum){return true;}
else{return false;}
}
return test(node->left,targetSum,nowSum + node->val)||test(node->right,targetSum,nowSum + node->val);
}
};
```
我们也可以只用一个函数，只要在递归过程的参数传递中不断把sum值减去当前节点值，在判断路径总和时直接判断 sum == root->val。
在不断把sum值减去当前节点值的过程中，如果当前节点来到路径总和为目标值的路径之末端，这个sum值必定等于当前节点值。
```c++
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);
}
};
```
#### 迭代法
在使用栈迭代遍历时，我们使用建值对替代节点压入栈，这个建值对有节点和到当前节点的路径和，这样我们就能在遍历中检测是否有目标路径值了。
#### 迭代法代码
```c++
class solution {
public:
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;
}
};
```
## 106.从中序与后序遍历序列构造二叉树
给定两个整数数组 `inorder` 和 `postorder` ，其中 `inorder` 是二叉树的中序遍历， `postorder` 是同一棵树的后序遍历，请你构造并返回这颗 *二叉树* 。
**示例 1:**
**输入：** inorder = \[9,3,15,20,7], postorder = \[9,15,7,20,3]**输出：**\[3,9,20,null,null,15,7]
**解法：递归**
首先后序遍历的最后一个元素就是根节点。
根据这个根节点，在中序遍历中划分出两段，前一段是根节点的左子树的中序遍历，右边是根节点的右子树的中序遍历，我们可以以根节点在中序遍历中的位置分割后序遍历，得到左子树的后序遍历和右子树的后序遍历。
此时我们可以通过子树的中序遍历和后序遍历继续这个过程，进入下一层递归。递归的返回值是子树的根节点，然后我们将根节点连接两个孩子。
递归的终止条件是此时后序遍历中只剩下一个元素（说明这个是叶子节点），直接返回这个元素，或者是后序遍历中没有元素，返回null。
#### 代码
```c++
class Solution {
private:
TreeNode* traversal (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;
}
// 切割中序数组
// 左闭右开区间：[0, delimiterIndex)
vector<int> leftInorder(inorder.begin(), inorder.begin() + delimiterIndex);
// [delimiterIndex + 1, end)
vector<int> rightInorder(inorder.begin() + delimiterIndex + 1, inorder.end() );
// postorder 舍弃末尾元素
postorder.resize(postorder.size() - 1);
// 切割后序数组
// 依然左闭右开，注意这里使用了左中序数组大小作为切割点
// [0, leftInorder.size)
vector<int> leftPostorder(postorder.begin(), postorder.begin() + leftInorder.size());
// [leftInorder.size(), end)
vector<int> rightPostorder(postorder.begin() + leftInorder.size(), postorder.end());
root->left = traversal(leftInorder, leftPostorder);
root->right = traversal(rightInorder, rightPostorder);
return root;
}
public:
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
if (inorder.size() == 0 || postorder.size() == 0) return NULL;
return traversal(inorder, postorder);
}
};
```
我们也可以不定义列表，直接使用下标来定位中序和后序遍历的内容：
```c++
class Solution {
private:
// 中序区间：[inorderBegin, inorderEnd)，后序区间[postorderBegin, postorderEnd)
TreeNode* traversal (vector<int>& inorder, int inorderBegin, int inorderEnd, vector<int>& postorder, int postorderBegin, int postorderEnd) {
if (postorderBegin == postorderEnd) return NULL;
int rootValue = postorder[postorderEnd - 1];
TreeNode* root = new TreeNode(rootValue);
if (postorderEnd - postorderBegin == 1) return root;
int delimiterIndex;
for (delimiterIndex = inorderBegin; delimiterIndex < inorderEnd; delimiterIndex++) {
if (inorder[delimiterIndex] == rootValue) break;
}
// 切割中序数组
// 左中序区间，左闭右开[leftInorderBegin, leftInorderEnd)
int leftInorderBegin = inorderBegin;
int leftInorderEnd = delimiterIndex;
// 右中序区间，左闭右开[rightInorderBegin, rightInorderEnd)
int rightInorderBegin = delimiterIndex + 1;
int rightInorderEnd = inorderEnd;
// 切割后序数组
// 左后序区间，左闭右开[leftPostorderBegin, leftPostorderEnd)
int leftPostorderBegin = postorderBegin;
int leftPostorderEnd = postorderBegin + delimiterIndex - inorderBegin; // 终止位置是 需要加上 中序区间的大小size
// 右后序区间，左闭右开[rightPostorderBegin, rightPostorderEnd)
int rightPostorderBegin = postorderBegin + (delimiterIndex - inorderBegin);
int rightPostorderEnd = postorderEnd - 1; // 排除最后一个元素，已经作为节点了
root->left = traversal(inorder, leftInorderBegin, leftInorderEnd, postorder, leftPostorderBegin, leftPostorderEnd);
root->right = traversal(inorder, rightInorderBegin, rightInorderEnd, postorder, rightPostorderBegin, rightPostorderEnd);
return root;
}
public:
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
if (inorder.size() == 0 || postorder.size() == 0) return NULL;
// 左闭右开的原则
return traversal(inorder, 0, inorder.size(), postorder, 0, postorder.size());
}
};
```