题目链接：513.找树左下角的值
给定一个二叉树的 根节点 root，请找出该二叉树的 最底层 最左边 节点的值。
假设二叉树中至少有一个节点。
文章讲解/视频讲解：https://programmercarl.com/0513.%E6%89%BE%E6%A0%91%E5%B7%A6%E4%B8%8B%E8%A7%92%E7%9A%84%E5%80%BC.html
采用层序遍历的方式实现，记录下遍历每层时的第一个节点的值left_val，随着一层层地遍历，left_val的值也在不断更新，最终获得的left_val的值便是树的左下角的值。
看了卡哥的题解之后，也可以采用递归的方式来处理。要找到树左下角的值，即寻找树的最后一行的最左边的值。当采用前序遍历（中序或后序亦可）时，遍历到的每一行的第一个节点就是每一行最左边的节点。因此可以采用递归的前序遍历来解，在每次遍历时记录当前深度，如果当前深度比之前记录的最大深度要大，那么说明此时来到了新的一行，当前访问的节点为新的一行的最左边的节点。
// 层序遍历求解
class Solution {
public:
int findBottomLeftValue(TreeNode* root) {
queue<TreeNode*> que;
int left_val = -1;
que.push(root);
while(!que.empty()){
int q_size = que.size();
for(int i = 0;i<q_size;i++){
TreeNode* cur = que.front();
que.pop();
if(i == 0) left_val = cur->val;
if(cur->left) que.push(cur->left);
if(cur->right) que.push(cur->right);
}
}
return left_val;
}
};
// 前序递归遍历求解
class Solution {
public:
int maxDepth;
int leftBottom;
int findBottomLeftValue(TreeNode* root) {
maxDepth = numeric_limits<int>::min();
dfs(root, 1);
return leftBottom;
}
void dfs(TreeNode* node, int depth){
if(depth > maxDepth){
maxDepth = depth;
leftBottom = node->val;
}
if(node->left) dfs(node->left, depth + 1);
if(node->right) dfs(node->right, depth + 1);
}
};
题目链接：112.路径总和
给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。
叶子节点 是指没有子节点的节点。
文章讲解/视频讲解：https://programmercarl.com/0112.%E8%B7%AF%E5%BE%84%E6%80%BB%E5%92%8C.html
用递归的方式来处理，递归函数携带当前已经累计的和，以及目标和，如果当前节点为叶子节点，且累计和与当前节点的值相加等于目标和，则说明找到了一个这样的节点，返回true。否则返回false。
也可以用迭代的方式来处理，用栈来模拟前序遍历，不过这时栈不仅要记录该节点指针，还要记录从头节点到该节点的路径数值总和。
// 递归实现
class Solution {
public:
bool hasPathSum(TreeNode* root, int targetSum) {
return traversal(root, 0, targetSum);
}
bool traversal(TreeNode* node, int curSum, const int& targetSum){
if(node == nullptr) return false;
if(node->left == nullptr && node->right == nullptr){
if(curSum + node->val == targetSum){
return true;
}
}
bool leftSuccess = traversal(node->left, curSum + node->val, targetSum);
bool rightSuccess = traversal(node->right, curSum + node->val, targetSum);
return leftSuccess || rightSuccess;
}
};
// 迭代实现
class Solution {
public:
bool hasPathSum(TreeNode* root, int targetSum) {
stack<pair<TreeNode*, int>> stk;
if(root == nullptr) return false;
stk.push({root, root->val});
while(!stk.empty()){
auto cur = stk.top();
stk.pop();
if(!cur.first->left && !cur.first->right && cur.second == targetSum){
return true;
}
if(cur.first->right){
stk.push({cur.first->right, cur.second + cur.first->right->val});
}
if(cur.first->left){
stk.push({cur.first->left, cur.second + cur.first->left->val});
}
}
return false;
}
};
顺便解决113.路径总和II
思路：
依然采用递归的思路，按照上题的方法，找到一条路径和等于目标和的路径，就加入结果中。
C++实现：
class Solution {
public:
vector<vector<int>> results;
vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
vector<int> paths;
traversal(root, 0, targetSum, paths);
return results;
}
void traversal(TreeNode* node, int curSum, const int& targetSum, vector<int>& paths){
if(node == nullptr) return;
paths.push_back(node->val);
if(!node->left && !node->right){
if(curSum + node->val == targetSum) results.push_back(paths);
}
else{
traversal(node->left, curSum + node->val, targetSum, paths);
traversal(node->right, curSum + node->val, targetSum, paths);
}
paths.pop_back();
}
};
题目链接：106.从中序与后序遍历序列构造二叉树
给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。
文章讲解/视频讲解：https://programmercarl.com/0106.%E4%BB%8E%E4%B8%AD%E5%BA%8F%E4%B8%8E%E5%90%8E%E5%BA%8F%E9%81%8D%E5%8E%86%E5%BA%8F%E5%88%97%E6%9E%84%E9%80%A0%E4%BA%8C%E5%8F%89%E6%A0%91.html
用递归的方法来做。递归函数traversal返回的是已经建立的子树的头节点，参数为包含该子树的inorder数组的范围 [ l 1 , r 1 ] [l_1, r_1] [l1?,r1?]，包含该子树的postorder数组的范围 [ l 2 , r 2 ] [l_2, r_2] [l2?,r2?]。
在每一次递归中，首先利用postorder数组找到头节点的值，当前范围的最后一个元素就是头节点，即下标 r 2 r_2 r2?处，根据头节点的值建立节点。
通过头节点的值在inorder数组中找到左右子树的分界，即，头节点左边的元素都属于左子树，右边的元素都属于右子树。
通过在inorder数组中找到的左右子树分界，划分postorder数组中左右子树的分界，即，在inorder中找到左子树的节点个数size，postorder数组中 [ l 2 , l 2 + s i z e ? 1 ] [l_2, l_2 + size - 1] [l2?,l2?+size?1]属于左子树， [ l 2 + s i z e , r 2 ? 1 ] [l_2 + size, r_2 - 1] [l2?+size,r2??1]属于右子树。
递归处理当前节点的左右子树，并把当前节点的left指向左子树，right指向右子树。
class Solution {
public:
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
return traversal(inorder, postorder, 0, inorder.size() - 1, 0, postorder.size() - 1);
}
TreeNode* traversal(const vector<int>& inorder, const vector<int>& postorder, int l1, int r1, int l2, int r2){
if(l1 > r1) return nullptr;
int headVal = postorder[r2];
TreeNode* head = new TreeNode(headVal);
int i;
for(i = l1;i<=r1;i++){
if(inorder[i] == headVal) break;
}
head->left = traversal(inorder, postorder, l1, i - 1, l2, l2 + i - l1 - 1);
head->right = traversal(inorder, postorder, i + 1, r1, l2 + i - l1, r2 - 1);
return head;
}
};
与此题类似的还有另外一道题，105. 从前序与中序遍历序列构造二叉树
思路：与上一题类似，也是采用递归的思路，在每一次递归的过程中，头节点为前序序列当前范围的第一个元素。
C++实现：
class Solution {
public:
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
return traversal(preorder, inorder, 0, preorder.size() - 1, 0, inorder.size() - 1);
}
TreeNode* traversal(const vector<int>& preorder, const vector<int>& inorder, int l1, int r1, int l2, int r2){
if(l1 > r1) return nullptr;
int headVal = preorder[l1];
TreeNode* head = new TreeNode(headVal);
int i;
for(i = l2;i<=r2;i++){
if(inorder[i] == headVal) break;
}
head->left = traversal(preorder, inorder, l1 + 1, l1 + i - l2, l2, i - 1);
head->right = traversal(preorder, inorder, l1 + i - l2 + 1, r1, i + 1, r2);
return head;
}
};