技术标签: 面试 算法 github 二叉树 ┈┈【剑指offer】 遍历
牛客OJ:二叉树的下一个结点
九度OJ:未收录
GitHub代码: 058-二叉树的下一个结点
CSDN题解:剑指Offer–058-二叉树的下一个结点
牛客OJ | 九度OJ | CSDN题解 | GitHub代码 |
---|---|---|---|
058-二叉树的下一个结点 | 未收录 | 剑指Offer–058-二叉树的下一个结点 | 058-二叉树的下一个结点 |
题目描述
给定一个二叉树和其中的一个结点,请找出中序遍历顺序的下一个结点并且返回。
注意,树中的结点不仅包含左右子结点,同时包含指向父结点的指针。
中序遍历的顺序是: 左 根 右
因此中序遍历中的下一个结点
比如结点2中序遍历的下一个结点是3
比如结点1中序遍历的下一个结点是2
比如结点3中序遍历的下一个结点是4
#include <iostream>
using namespace std;
// 调试开关
#define __tmain main
#ifdef __tmain
#define debug cout
#else
#define debug 0 && cout
#endif // __tmain
using namespace std;
#ifdef __tmain
struct TreeLinkNode
{
int val;
struct TreeLinkNode *left;
struct TreeLinkNode *right;
struct TreeLinkNode *next;
TreeLinkNode(int x = 0)
:val(x), left(NULL), right(NULL), next(NULL)
{
}
};
#endif // __tmain
class Solution {
public:
TreeLinkNode* GetNext(TreeLinkNode* pNode)
{
if(pNode == NULL)
{
return NULL;
}
TreeLinkNode *pNext = NULL;
// 如果当前结点有右子树, 那么其中序遍历的下一个结点就是其右子树的最左结点
if(pNode->right != NULL)
{
// 找到右子树的最左孩子
pNext = pNode->right;
while(pNext->left != NULL)
{
pNext = pNext->left;
}
}
else if(pNode->right == NULL && pNode->next != NULL)
{
TreeLinkNode *pCurrent = pNode;
TreeLinkNode *pParent = pNode->next;
// 如果当前结点是其父结点的左子结点那么其中序遍历的下一个结点就是他的父亲结点
//
// 如果当前结点是其父结点的右子结点
// 这种情况下其下一个结点应该是当前结点所在的左子树的根
// 因此我们可以顺着其父节点一直向上遍历
// 直到找到一个是它父结点的左子结点的结点
while(pParent != NULL && pCurrent == pParent->right)
{
pCurrent = pParent;
pParent = pParent->next;
}
pNext = pParent;
}
return pNext;
}
};
/*
void InOrder(TreeLinkNode *tree)
{
if(tree == NULL)
{
return;
}
InOrder(tree->left);
cout <<tree->val;
InOrder(tree->right);
}
*/
int __tmain( )
{
Solution solu;
TreeLinkNode tree[10];
tree[0].val = 4;
tree[0].left = &tree[1];
tree[0].right = &tree[2];
tree[0].next = NULL;
tree[1].val = 2;
tree[1].left = &tree[3];
tree[1].right = &tree[4];
tree[1].next = &tree[0];
tree[2].val = 5;
tree[2].left = NULL;
tree[2].right = &tree[5];
tree[2].next = &tree[0];
tree[3].val = 1;
tree[3].left = &tree[6];
tree[3].right = NULL;
tree[3].next = &tree[1];
tree[4].val = 3;
tree[4].left = NULL;
tree[4].right = NULL;
tree[4].next = &tree[1];
tree[5].val = 9;
tree[5].left = &tree[7];
tree[5].right = NULL;
tree[5].next = &tree[2];
tree[6].val = 0;
tree[6].left = NULL;
tree[6].right = NULL;
tree[6].next = &tree[3];
tree[7].val = 7;
tree[7].left = &tree[8];
tree[7].right = &tree[9];
tree[7].next = &tree[5];
tree[8].val = 6;
tree[8].left = NULL;
tree[8].right = NULL;
tree[8].next = &tree[7];
tree[9].val = 8;
tree[9].left = NULL;
tree[9].right = NULL;
tree[9].next = &tree[7];
//InOrder(tree);
cout <<solu.GetNext(&tree[6])->val <<endl;;
cout <<solu.GetNext(&tree[3])->val <<endl;;
cout <<solu.GetNext(&tree[1])->val <<endl;
cout <<solu.GetNext(&tree[4])->val <<endl;;
cout <<solu.GetNext(&tree[0])->val <<endl;
cout <<solu.GetNext(&tree[2])->val <<endl;
cout <<solu.GetNext(&tree[8])->val <<endl;
cout <<solu.GetNext(&tree[7])->val <<endl;
cout <<solu.GetNext(&tree[9])->val <<endl;
return 0;
}
文章浏览阅读75次。作者 |杨智钦单位 |北京航空航天大学来源|将门创投在本文中,我们提出了一种新的即插即用的联邦学习模块,FedFed,其能够以特征蒸馏的方式来解决联邦场景下的数据异构问题。FedFed首次探索了对数据中部分特征的提取与分享,大量的实验显示,FedFed能够显著地提升联邦学习在异构数据场景下的性能和收敛速度。论文标题:FedFed: Feature Distillation against..._about [neurips 2023] "fedfed: feature distillation against data heterogeneit
文章浏览阅读3k次,点赞2次,收藏3次。《Ray Tracing in One Weekend》目录 第一部分:学习总结问题二:用C++输出第一张图片 第二部分:原文截图《Ray Tracing in One Weekend》目录_c++如何输出图片
文章浏览阅读8k次,点赞7次,收藏9次。spring-cloud-kubernetes-config是spring-cloud-kubernetes框架下的一个库,用于将kubernetes的configmap作为配置文件,提供给springboot应用_spring-cloud-starter-kubernetes-config maven
文章浏览阅读307次。传送门题意: n个有高度的点和m条边,边只能从高点到低点走,求最小树形图??题解: 最小生成树。 朱刘算法求最小树形图只能得70分,考虑更高效的算法。首先对图分层,发现低层节点对高层答案没有影响,考虑先处理高层的边。现在假设已经处理了高层的所有边,对于本层的边,其实就是一颗最小生成树。因为高层连向本层的边看做双向边没有任何影响。那么直接把边按照层数排序,第二关键字用权值排序即可。#includ
文章浏览阅读1.3k次。python GUI开发中PySide2、PySide6及PyQt间区别,python版本要求,官方文档支持等_pyside
文章浏览阅读3.3k次,点赞4次,收藏19次。Hough变换思想(参数空间变换):在原始图像坐标系下的一个点对应了参数坐标系中的一条直线,同样参数坐标系的一条直线对应了原始坐标系下的一个点,然后,原始坐标系下呈现直线的所有点,它们的斜率和截距是相同的,所以它们在参数坐标系下对应于同一个点。这样在将原始坐标系下的各个点投影到参数坐标系下之后,看参数坐标系下有没有聚集点,这样的聚集点就对应了原始坐标系下的直线。在实际应用中,y=kx+b形式..._opencv python hough_multi_scale
文章浏览阅读10w+次,点赞565次,收藏2.9k次。vs2019安装和使用教程(详细)_vs2019
文章浏览阅读2.5k次,点赞2次,收藏2次。《JAVA程序设计》作业一、选择题编译HelloWorld.java的正确命令是:java HelloWorld.class B)java HelloWorld.java C)javac HelloWorld.java正确运行HelloWorld.java的正确命令是:java HelloWorld B)javac HelloWorld.java C)javac HelloWorld.class下面程序代码,使用多行注释正确的是:A) // int k=9;// int j=8_which of the following are correct? _____ a. string[] list = new string{
文章浏览阅读812次。注:本文转自赛灵思中文社区论坛,源文链接在此。本文原作者为XILINX工程师。以下为个人译文,仅供参考,如有疏漏之处,还请不吝赐教。本篇博文提供了一份视频列表,用于展示 (UG1209) 中的教程。这些视频是使用 Vivado Design Suite 2019.1 版和赛灵思软件开发套件 (SDK) 创建的。其中所含示例均为针对 Zynq UltraScale+ MPSoC ZCU102 Rev1 评估板的示例。视频 1 演示了如何使用 ZCU102 评估板来运行应用。虽然大部分视频都使_zynq ultrascale+ mpsoc 嵌入式设计方法指南
文章浏览阅读284次。拉格朗日插值法_y_j_gi
文章浏览阅读263次。_hfile.format.version
文章浏览阅读896次。本栏目(Algorithms)下MIT算法导论专题是个人对网易公开课MIT算法导论的学习心得与笔记。所有内容均来自MIT公开课Introduction to Algorithms中Charles E. Leiserson和Erik Demaine老师的讲解。(http://v.163.com/special/opencourse/algorithms.html)第五节-------线性时间_linear time sorting