513. 找树左下角的值
题目描述
给定一个二叉树的 根节点 root，请找出该二叉树的 最底层 最左边 节点的值。
假设二叉树中至少有一个节点。
示例 1:
输入: root = [2,1,3]
输出: 1
示例 2:
输入: [1,2,3,4,null,5,6,null,null,7]
输出: 7
提示:
- 二叉树的节点个数的范围是
[1,104] -231 <= Node.val <= 231 - 1
题解
题目说的很清楚了，目标先是 “最底层” ，再是 “最左边” ，所以考虑先用层序遍历得到最底层的节点值数组，然后返回数组第一个值，即为“左下角”的值了：
vector<vector<int>> levelOrder(TreeNode *root)
{
vector<vector<int>> res;
queue<TreeNode *> q;
if (!root)
return res;
q.push(root);
while (!q.empty())
{
int size = q.size(); // 注意！先记录当前队长，因为之后会变
vector<int> level; // 当前这一层的节点值
for (int i = 0; i < size; ++i)
{
level.push_back(q.front()->val);
if (q.front()->left)
q.push(q.front()->left);
if (q.front()->right)
q.push(q.front()->right);
q.pop();
}
res.push_back(level);
}
return res;
}
int findBottomLeftValue(TreeNode *root)
{
vector<vector<int>> levels = levelOrder(root); // 偷个懒，直接调用之前写过的层序遍历函数
return levels[levels.size() - 1][0];
}
此外，我们还是可以考虑一下递归法，逐步递归到左下角。递归出口的判断也比较简单，即：若当前节点的左孩子是叶子节点，则根据其深度判断是否要更新左下角值：
int maxDepth = -1;
int leftBottonVal = 0;
void traversal(TreeNode *root, int depth)
{
// 递归出口：叶子节点
if (!root->left && !root->right && depth > maxDepth)
{
leftBottonVal = root->val; // 更新当前探索到的左下角值
maxDepth = depth; // 更新当前探索到的最大深度
return;
}
// 先处理左孩子，这样保证同一层记录最左节点
if (root->left)
traversal(root->left, depth + 1);
// 再处理右孩子
if (root->right)
traversal(root->right, depth + 1);
}
int findBottomLeftValue_II(TreeNode *root)
{
traversal(root, 0);
return leftBottonVal;
}
112. 路径总合
题目描述
给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。
叶子节点 是指没有子节点的节点。
示例 1：
输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
输出：true
解释：等于目标和的根节点到叶节点路径如上图所示。
示例 2：
输入：root = [1,2,3], targetSum = 5
输出：false
解释：树中存在两条根节点到叶子节点的路径：
(1 --> 2): 和为 3
(1 --> 3): 和为 4
不存在 sum = 5 的根节点到叶子节点的路径。
示例 3：
输入：root = [], targetSum = 0
输出：false
解释：由于树是空的，所以不存在根节点到叶子节点的路径。
提示：
- 树中节点的数目在范围
[0, 5000]内 -1000 <= Node.val <= 1000-1000 <= targetSum <= 1000
题解
首先可以用DFS递归秒杀：
bool hasPathSum(TreeNode *root, int targetSum)
{
// 递归出口1：空节点
if (!root)
return false;
// 递归出口2：加上当前节点值求和等于targetSum，且当前节点为叶子节点
if (root->val == targetSum && !root->left && !root->right)
return true;
// 递归探索左右子树
return hasPathSum(root->left, targetSum - root->val) || hasPathSum(root->right, targetSum - root->val);
}
然后再想想迭代法，发现这题和 257. 二叉树的所有路径 其实如出一辙（具体思路和注意细节见那篇题解），只需要将其中记录路径的逻辑替换成计算路径节点值之和就行了：
bool hasPathSum_II(TreeNode *root, int targetSum) {
// 基于前序遍历的统一迭代法实现
if (!root)
return false;
stack<TreeNode*> nodeSt;
nodeSt.push(root);
stack<int> sumSt;
sumSt.push(root->val);
while (!nodeSt.empty()) {
TreeNode *node = nodeSt.top();
nodeSt.pop();
int sum = sumSt.top();
sumSt.pop();
if (node) {
if (node->right) {
nodeSt.push(node->right); // 右
sumSt.push(sum + node->right->val);
}
if (node->left) {
nodeSt.push(node->left); // 左
sumSt.push(sum + node->left->val);
}
nodeSt.push(node); // 中
nodeSt.push(nullptr); // 空指针标记
sumSt.push(sum);
}
else {
if (sum == targetSum && !nodeSt.top()->left && !nodeSt.top()->right)
return true;
nodeSt.pop();
}
}
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]
示例 2:
输入：inorder = [-1], postorder = [-1]
输出：[-1]
提示:
1 <= inorder.length <= 3000postorder.length == inorder.length-3000 <= inorder[i], postorder[i] <= 3000inorder和postorder都由 不同 的值组成postorder中每一个值都在inorder中inorder保证是树的中序遍历postorder保证是树的后序遍历
题解
蛮锻炼思维的一道题目
我觉得核心是要理解两点：
1️⃣ 中序序列 inorder 的第 i 个值对应的节点，其左、右子树中的节点对应的就是 i 左边、右边的序列
2️⃣ 后序序列 postorder 的最后一个值，就是该序列对应的二叉树的根节点
这两点不难由中序遍历和后序遍历的定义和性质得出。于是，我们可以据此从根节点递归地“生长”出二叉树：
-
取
postorder的最后一个值r为根节点root的值 -
在
inorder中找到r对应的下标i，则i左边的值就对应着root的左子树、i右边的值就对应着root的右子树题目说了：
inorder和postorder都由 不同 的值组成，所以可以根据数值（唯一）对应去找下标 -
以
i为“分割点”，将inorder拆分为左右两部分；相应地也将postorder拆分，满足- 排除
postorder的最后一个值（因为它是分割点，对应着当前根节点） postorder的左右部分长度和inorder的左右部分长度相同
- 排除
-
按照上述方法递归地生成
root的左右子树，递归出口为序列切片已经不可分割则返回空指针
此思路更详细的分析可参阅 代码随想录此题讲解 。我的代码如下，包括了一个调试函数 log ，用于debug的时候检查每次生成的中序、后序左右子序列长度是否一致、数值是否一一对应（即它们都表示着同一棵子树）：
class Solution
{
private:
// 由于所有值各不相同，先用哈希表存储其在中序、后序数组中的下标
unordered_map<int, int> inMap, postMap;
void getIndexMap(const vector<int> &inorder, const vector<int> &postorder)
{
for (int i = 0; i < inorder.size(); ++i)
{
inMap[inorder[i]] = i;
postMap[postorder[i]] = i;
}
}
// todo debug
void log(
const vector<int> &inorder, const vector<int> &postorder,
int inLeftB, int inLeftE, int inRightB, int inRightE,
int postLeftB, int postLeftE, int postRightB, int postRightE)
{
cout << "----------inorder left----------" << endl;
for (int i = inLeftB; i < inLeftE; ++i)
cout << inorder[i] << " ";
cout << endl;
cout << "---------postorder left---------" << endl;
for (int i = postLeftB; i < postLeftE; ++i)
cout << postorder[i] << " ";
cout << endl;
cout << "----------inorder right---------" << endl;
for (int i = inRightB; i < inRightE; ++i)
cout << inorder[i] << " ";
cout << endl;
cout << "-----------post right-----------" << endl;
for (int i = postRightB; i < postRightE; ++i)
cout << postorder[i] << " ";
cout << endl;
cout << "********************************" << endl;
}
public:
/// @brief 根据中序、后序数组的切片（左闭右开），递归获取树中的节点
/// @param postorder 后序遍历数组（用于初始化当前的新节点）
/// @param inBegin 当前中序数组的起始指针
/// @param inEnd 当前中序数组的结尾指针
/// @param postBegin 当前后序数组的起始指针
/// @param postEnd 当前后序数组的结尾指针
/// @return 当前获得的节点
TreeNode *getNode(
const vector<int> &inorder, const vector<int> &postorder,
int inBegin, int inEnd, int postBegin, int postEnd)
{
if (inBegin == inEnd)
return nullptr;
// 后序数组的最后一个值，就是当前子树根节点的值
TreeNode *root = new TreeNode(postorder[postEnd - 1]);
// 定位该节点在中序数组中的位置，作为分割点
int cutPoint = inMap[root->val];
// 将中序数组拆分，则root的左右子树对应节点值也就是拆分后的左右部分
int leftInBegin = inBegin, leftInEnd = cutPoint; // 左半部分
int rightInBegin = cutPoint + 1, rightInEnd = inEnd; // 右半部分
// 相应的，将后序数组也按照同样位置拆分
int leftPostBegin = postBegin, leftPostEnd = postBegin + (cutPoint - inBegin); // 左半部分
int rightPostBegin = postBegin + (cutPoint - inBegin), rightPostEnd = postEnd - 1; // 右半部分
// log(
// inorder, postorder,
// leftInBegin, leftInEnd, rightInBegin, rightInEnd,
// leftPostBegin, leftPostEnd, rightPostBegin, rightPostEnd
// );
// 获取当前root的左右子树，然后返回当前root
root->left = getNode(
inorder, postorder, leftInBegin, leftInEnd, leftPostBegin, leftPostEnd);
root->right = getNode(inorder, postorder, rightInBegin, rightInEnd, rightPostBegin, rightPostEnd);
return root;
}
// 递归、多指针解决
TreeNode *buildTree(vector<int> &inorder, vector<int> &postorder)
{
getIndexMap(inorder, postorder);
return getNode(inorder, postorder, 0, inorder.size(), 0, postorder.size());
}
};
上面的写法比较便于理解算法和调试，将 log 那部分代码注释取消，运行题目描述中的示例1，可以看到每次递归生成的子序列。以第一次分割为例，有输出：
----------inorder left----------
9
---------postorder left---------
9
----------inorder right---------
15 20 7
-----------post right-----------
15 7 20
********************************
...
可以看到，中序、后序的左、右子序列都是一一对应的。
实际上，后序遍历的左右子序列没必要每次都全部维护，可以发现代码中我们实际用到的也就是其尾指针（每次指向当前的根节点）。所以可以简化代码如下（来源：LeetCode官方题解）：
class Solution {
int post_idx;
unordered_map<int, int> idx_map;
public:
TreeNode* helper(int in_left, int in_right, vector<int>& inorder, vector<int>& postorder){
// 如果这里没有节点构造二叉树了，就结束
if (in_left > in_right) {
return nullptr;
}
// 选择 post_idx 位置的元素作为当前子树根节点
int root_val = postorder[post_idx];
TreeNode* root = new TreeNode(root_val);
// 根据 root 所在位置分成左右两棵子树
int index = idx_map[root_val];
// 下标减一
post_idx--;
// 构造右子树
root->right = helper(index + 1, in_right, inorder, postorder);
// 构造左子树
root->left = helper(in_left, index - 1, inorder, postorder);
return root;
}
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
// 从后序遍历的最后一个元素开始
post_idx = (int)postorder.size() - 1;
// 建立（元素，下标）键值对的哈希表
int idx = 0;
for (auto& val : inorder) {
idx_map[val] = idx++;
}
return helper(0, (int)inorder.size() - 1, inorder, postorder);
}
};
作者：力扣官方题解
链接：https://leetcode.cn/problems/construct-binary-tree-from-inorder-and-postorder-traversal/solutions/426738/cong-zhong-xu-yu-hou-xu-bian-li-xu-lie-gou-zao-14/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
本站资源均来自互联网，仅供研究学习，禁止违法使用和商用，产生法律纠纷本站概不负责！如果侵犯了您的权益请与我们联系！
转载请注明出处： 免费源码网-免费的源码资源网站 » 24暑假算法刷题 | Day16 | LeetCode 513. 找树左下角的值，112. 路径总合，106. 从中序和后序遍历序列构造二叉树
发表评论 取消回复