剑指57-二叉树的下一个结点
2023-02-18 16:41:10 时间
中序遍历
题目描述
给定一个二叉树和其中的一个结点,请找出中序遍历顺序的下一个结点并且返回。注意,树中的结点不仅包含左右子结点,同时包含指向父结点的指针。
其实刚开始做题我还是有点迷惑的,按理说这个算法的参数不应该是给出一个二叉树和一个结点吗,而这里只给了一个参数,后来想了一下,这个参数不仅是一个二叉树,同时也是要指定的要找下一个结点的结点
解法
- 如果有右结点,下一个就是右子树的最左结点
- 如果没有右结点,而且是父节点的左结点
- 如果没有右结点,而且是父节点的右结点,则应该找到其祖先结点里,第一个该祖先结点为其父节点的左结点的这样一个结点,听起来有点拗口
我们分别来看看这三种情况
情况1:如果有右结点,下一个就是右子树的最左结点,这个应该比较好理解
情况2:如果没有右结点,而且是父节点的左结点
情况3:如果没有右结点,而且是父节点的右结点
代码
struct TreeLinkNode {
int val;
struct TreeLinkNode *left;
struct TreeLinkNode *right;
struct TreeLinkNode *next;
TreeLinkNode(int x) :val(x), left(nullptr), right(nullptr), next(nullptr) {
}
};
class Solution {
public:
TreeLinkNode* GetNext(TreeLinkNode* pNode)
{
if (!pNode) return pNode;
if (pNode->right) return inorderTraverse(pNode->right); //如果有右结点,下一个就是右子树的最左结点
else if (pNode->next && pNode->next->left == pNode) { //如果没有右结点,而且是父节点的左结点
return pNode->next;
}
else if (pNode->next && pNode->next->right == pNode) //如果没有右结点,而且是父节点的右结点
{
//这里是个难点,应该找到其祖先结点里,第一个该祖先结点为其父节点的左结点的这样一个结点,听起来有点拗口
while (pNode->next) {
TreeLinkNode *root = pNode->next;
if (root->left == pNode) {
return root;
}
pNode = pNode->next;
}
}
return nullptr;
}
TreeLinkNode* inorderTraverse(TreeLinkNode* root) //找到最左的结点
{
if (!root) return root;
if (root->left) return inorderTraverse(root->left);
else return root;
}
};
相关文章
- 不藏了,这些Java反射用法总结都告诉你们
- java算法易筋经:常见java-API使用技巧
- 论文/代码速递2022.10.19!
- 论文/代码速递2022.10.20!
- 【AI绘画】如何优雅的在本地配置 nounovelai ?
- 英伟达最新成果!基于NeRF的并行优化方法,可用于6D姿态估计!论文/代码速递2022.10.21!
- 论文/代码速递2022.10.24!
- 低分辨率人脸识别!注意力相似性知识提取方法!论文/代码速递2022.10.25!
- 论文/代码速递2022.10.26!
- ECCV 2022 | 开放集半监督目标检测!论文/代码速递2022.10.27!
- 论文/代码速递2022.10.28!
- SCI语料库!学术写作神器——Academic Phrasebank
- 查找表实现高效的图像超分辨率!论文/代码速递2022.10.31!
- 论文/代码速递2022.11.1!
- ECCV2022 | 通过网格实现辐射场的自由变形! 已开源!论文/代码速递2022.11.2!
- DELTAR:轻量级 ToF 传感器和 RGB 图像的深度估计!论文/代码速递2022.11.3!
- AI绘画!英伟达最新文图生成模型!质量优于Stable Diffusion和Dalle2!论文/代码速递2022.11.4!
- 论文/代码速递2022.11.7!
- 论文/代码速递2022.11.8!
- FactorMatte:最新视频抠图算法,更适合于视频合成任务!论文/代码速递2022.11.9!