剑指offer-08 二叉树的下一个节点
2024-10-19 05:11:24
剑指offer第8题，本来想找leetcode上对应的题，后来没找到，直接去牛客网上刷了。
题目描述：
给定一个二叉树和其中的一个结点(pNode)，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。
分析
我看到这道题的第一个想法，就是不用管左子树。因为中序遍历，左子树是之前访问过了，所以下一个节点只有两种可能。
一、在右子树
二、在父亲节点的部分
分情况讨论：
一、在右子树
如果右子树只有一个节点那还好说，那么下一个节点就是右子节点。但是如果右子树是一个树，那么就得看右子树的最左节点。
TreeLinkNode * point=pNode->right;
while(point->left!=NULL)
{
point=point->left;
}
return point;
二、在父亲节点之上
若右子树为空，此时分两种情况。
（1）pNode是父亲节点的左子节点，那正好，下一个要访问的就是父亲节点，直接返回父亲节点就行；
（2）pNode是父亲节点的右子节点，说明下一个节点所在的区域，还至少在父亲节点的父亲节点之上。
我一开始绕了个远，第二种情况，我想到的是用递归解决。如果pNode是父亲节点的右子节点，那么就pNode=pNode->next;同时砍去父亲节点的右子树。这样就构造了一个子问题，把问题转换成了给定父亲节点之后，寻找访问下一个节点的问题。
if(pNode->right==NULL)
{
if(pNode->next==NULL||pNode==pNode->next->left)
return pNode->next;
else{
pNode->next->right=NULL;
return GetNext(pNode->next);
}
}
说的有点绕，整体思想就是砍去右子树，让指针指向父亲，然后在新的树里,寻找指针指向的节点要访问的下一个节点。其实我个人觉得还挺巧妙的。
不过还是把简单问题复杂化了，其实直接一直往父亲寻找就行，直到找到满足情况（1）的pNode，返回pNode->next。
if(pNode->right==NULL)
{
while(pNode->next!=NULL&&pNode!=pNode->next->left)
pNode=pNode->next;
return pNode->next;
}
最后放一下整体代码：
/*
struct TreeLinkNode {
int val;
struct TreeLinkNode *left;
struct TreeLinkNode *right;
struct TreeLinkNode *next;
TreeLinkNode(int x) :val(x), left(NULL), right(NULL), next(NULL) {
}
};
*/
class Solution {
public:
TreeLinkNode* GetNext(TreeLinkNode* pNode)
{
if(pNode==NULL)
return NULL;
if(pNode->right==NULL)
{
while(pNode->next!=NULL&&pNode!=pNode->next->left)
pNode=pNode->next;
return pNode->next;
}
TreeLinkNode * point=pNode->right;
while(point->left!=NULL)
{
point=point->left;
}
return point;
}
};
最新文章
- Hibernate（6）—— 一对多 和 多对多关联关系映射（xml和注解）总结
- eclispe+axis2+webservice入门
- Conquer and Divide经典例子之汉诺塔问题
- java获取当前日期等以及时区
- Docker ntpdate Permition error
- js正则表达式练习
- eclipse快捷键调试总结【转】
- Cpdetector编码识别
- springmvc学习笔记--REST API的异常处理
- IOS开展：导航中添加多个button并加入左侧logo
- .net图片快速去底（去除白色背景）
- .Net Web开发技术栈
- nyoj 概率计算
- SharePoint布局页创建（实战）
- spring注解-“@Scope”
- python脚本在linux下的执行
- Web前端JQuery面试题（三）
- 13LaTeX学习系列之---LaTeX插入表格
- Vue.js——60分钟组件快速入门（下篇）
- C#文件夹权限操作工具类