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 <= 3000
postorder.length == inorder.length
-3000 <= inorder[i], postorder[i] <= 3000
inorder
和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)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。