【题目】给定一个二叉树和其中的一个结点,请找出中序遍历顺序的下一个结点并且返回。
注意,树中的结点不仅包含左右子结点,同时包含指向父结点的指针。
package com.exe7.offer; /**
* 【题目】给定一个二叉树和其中的一个结点,请找出中序遍历顺序的下一个结点并且返回。
* 注意,树中的结点不仅包含左右子结点,同时包含指向父结点的指针。
* @author WGS
*
*/
public class GetNextNode { public class TreeNode{
int val;
TreeNode left=null;
TreeNode right=null;
TreeNode next=null;
public TreeNode(int val){
this.val=val;
}
} public TreeNode getNextNode(TreeNode pNode){
if(pNode==null) return null;
//1 判断有无右子树,有就是右子树最左子节点;
TreeNode curNode=null;
if(pNode.right!=null){
curNode=pNode.right;
while(curNode.left!=null){
curNode=curNode.left;
}
return curNode;
}
//2 无右子树;
else{
//1) 判断该结点是否是其父节点的左结点,是,下个结点就是其父节点。
if(pNode.next==null) return null;
if(pNode==pNode.next.left){
return pNode.next;//返回其父节点
} //2) 该结点不是父节点的左结点即是其右节点,则判断其父节点是否是父父结点的左结点;
curNode=pNode.next;//该结点的父节点
while(curNode.next!=null){
if(curNode==curNode.next.left){
return curNode.next;//返回其父节点的父节点
}
curNode=curNode.next;//继续回溯
}
} return null; }
}
剑指offer系列31-----二叉树的下一个节点的更多相关文章
-
【剑指offer】08二叉树的下一个节点,C++实现
原创博文,转载请注明出处! # 题目 父节点指向子节点的指针用实线表示,从子节点指向父节点的指针用虚线表示. # 思路 如果节点有右子节点,则右子节点的最左节点是该节点的下一个节点.例如,寻找b的下一 ...
-
【剑指 Offer】08.二叉树的下一个节点
题目描述 给定一颗二叉树和其中的一个节点,找出中序遍历序列的下一个节点.树中的节点除了有两个分别指向左右节点的指针,还有一个指向父节点的指针. Java public class Solution08 ...
-
剑指offer:JZ8 二叉树的下一个结点
JZ8 二叉树的下一个结点 描述 给定一个二叉树其中的一个结点,请找出中序遍历顺序的下一个结点并且返回.注意,树中的结点不仅包含左右子结点,同时包含指向父结点的next指针.下图为一棵有9个节点的二叉 ...
-
【剑指Offer】58:二叉树的下一个结点
题目描述 给定一个二叉树和其中的一个结点,请找出中序遍历顺序的下一个结点并且返回.注意,树中的结点不仅包含左右子结点,同时包含指向父结点的指针. 题解一:递归 //既然给了二叉树的某个结点,且二叉树存 ...
-
《剑指offer》-中序遍历下一个节点
题目描述 给定一个二叉树和其中的一个结点,请找出中序遍历顺序的下一个结点并且返回.注意,树中的结点不仅包含左右子结点,同时包含指向父结点的指针. /* struct TreeLinkNode { in ...
-
剑指offer-面试题8-二叉树的下一个节点-二叉树
/* 题目: 给定一棵二叉树和其中一个节点,找出中序遍历的下一个节点. */ /* 思路: 两种情况: 节点存在右子树:节点右子树的最左节点: 节点不存在右子树,节点向上一直找父节点或祖父节点,直到其 ...
-
剑指offer系列20--从上到下打印二叉树
* 20 [题目]从上往下打印出二叉树的每个节点,同层节点从左至右打印. * [思路]从根结点开始,先保存结点,再看根结点的左右结点有没有值. * 有,就将左右值放到集合中: * 根节点输出后,打印根 ...
-
剑指offer系列33-----把二叉树打印成多行
[题目]从上到下按层打印二叉树,同一层结点从左至右输出.每一层输出一行. 方法一:直接打印 package com.exe7.offer; import java.util.LinkedList; i ...
-
剑指offer系列29-----链表中环的入口节点-
[题目]一个链表中包含环,请找出该链表的环的入口结点. [思路]方法一:使用双指针 方法二:利用set集合的特性,不能添加重复数字,否则返回false package com.exe7.offer; ...
随机推荐
- xcode 6 创建的工程上下有黑边
-
Jenkins 插件 CIFS
Jenkis编译后我们往往需要把文件发布的其他的服务器上,典型的插件如下: Publish Over CIFS Plugin Publish Over FTP Plugin Publish ...
-
c语言中的部分字符串和字符函数
// // main.c // homeWork1230 // // #include <stdio.h> #include <string.h> #include <c ...
-
九度 OJ1008 hdu 3790
#include<stdio.h> #include<string.h> struct node { int d; int p; }g[][]; #define inf 0x3 ...
-
vmware lan map
1,nat: virtrual machine---vmnet8---PC---internet 2,host-only virtual machine(0,1,2...)---vmnet1 3,br ...
-
magento关于站点搬家,换空间
1,先把原来空间的文件全部压缩后(有些不要的就不要压缩)下载下来,然后传到新空间去,注意下载下来后核对一下是否大小一样,建议使用ftp工具下载, 2,同样把原来空间的数据库打包下来,再在新空间创建一个 ...
-
观察者模式(Observer)和发布(Publish/订阅模式(Subscribe)的区别
观察者模式(Observer)和发布(Publish/订阅模式(Subscribe)的区别 在翻阅资料的时候,有人把观察者(Observer)模式等同于发布(Publish)/订阅(Subscribe ...
-
Python——Sublime Text3编写Python的一些问题
1.回车键不能结束input()函数,如何解决? https://www.cnblogs.com/pcat/p/5499964.html 安装了该插件后,会遇到一些麻烦,这样运行Python程序很不 ...
-
MGR架构~ 整体性能架构的调优
一 简介:MGR集群架构的调优二 过程:本文将从各个角度来具体阐述下三 硬件 1 硬件选择相同配置的服务器,磁盘,内存,cpu性能越高越好四 网络 1 0丢包和最好万兆网卡五 MGR本身 ...
-
20145236《网络对抗》Exp9 web安全基础实践
20145236<网络对抗>Exp9 web安全基础实践 一.基础问题回答: SQL注入攻击原理,如何防御 SQL Injection:就是通过把SQL命令插入到Web表单递交或输入域名或 ...