给定树的根结点指针TreeNode* root和结点的值int p，编写一个函数，寻找该二叉树中指定结点的下一个结点（即中序遍历的后继），并返回p结点的后继结点的值。保证结点的值是小于等于100000的正数且没有重复值，若不存在后继返回-1。
[编程题]寻找下一个结点
《程序员面试金典》--题目代码详解：
题目分析：
要寻找中序遍历的某个节点的下一个节点，肯定是要通过中序遍历实现的，题目中明确告诉我们节点的值没有重复，所以只要在中序遍历的过程中，某个节点的值等于p，则告诉递归者下一个要遍历的节点便是我们要找的节点，这个需要有个信号在多次递归之间进行传递消息，c++里用引用完全可以实现，只需要传递一个bool类型的引用便可。
程序实现代码：
class Successor {
public:
int findSucc(TreeNode* root, int p) {
// write code here
bool sign=0;
return findSucc1(root,p,sign);
}
int findSucc1(TreeNode* root,int p,bool &sign)
{
if(root==NULL)
return -1;
int left=findSucc1(root->left,p,sign);
if(left!=-1)
return left;
if(sign==true)
return root->val;
if(root->val==p)
sign=true;
return findSucc1(root->right,p,sign);
}
};
发表于 2015-10-25 14:19:56
回复(5)
import java.util.*;
/*
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}*/
public class Successor {
public int findSucc(TreeNode root, int p) {
boolean isFound = false;
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode cur = root;
while(cur!=null||!stack.isEmpty()){
while(cur!=null){
stack.add(cur);
cur = cur.left;
}
if(!stack.isEmpty()){
TreeNode q = stack.pop();
if(isFound) return q.val;
else if(q.val==p) isFound = true;
cur = q.right;
}
}
return -1;
}
}
中序遍历非递归算法
发表于 2015-07-29 14:23:03
回复(0)
/*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};*/
class Successor {
public:
int findSucc(TreeNode* root, int q) {
if(root==NULL) return -1;
stack<TreeNode*> stk;
TreeNode *p=root;
int k=1;
while(!stk.empty()||p)
{
if(p!=NULL)
{
stk.push(p);
p=p->left;
}
else
{
p=stk.top(); stk.pop();
if(k==0)
{
return p->val;
}
if(p->val==q)
{
k--;
}
p=p->right;
}
}
return -1;
}
};
发表于 2016-04-18 21:36:19
回复(0)
import java.util.*;
/*
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}*/
public class Successor {
//前一个节点，令此引用按照中序遍历的来移动，利用它来进行逆向移动
//即原来只能是 根→左 现在可以 左→根
private TreeNode pre = new TreeNode(-1);
public int findSucc(TreeNode root, int p) {
//空则表示没有
if (root == null)
return -1;
//一路向左，到达最左边的叶子
int left = findSucc(root.left, p);
if (left == -1) {
//最开始到达最左节点后，令pre指向该节点，同时root为pre的后继节点
////其后按照左根右的顺序移动
//如果上一个节点中找到p，则该节点后其后继节点
if (pre.val == p) {
return root.val;
}
pre = root; //如果前一个节点不是，则pre指向root的对象，
return findSucc(root.right, p);
}
//如果找不到则返回上一层的根节点，方向为 左→根
return left;
}
}
发表于 2015-09-04 21:16:03
回复(0)
public int findSucc(TreeNode root, int p) {
// 非递归中序遍历，栈
Stack<TreeNode> list = new Stack<TreeNode>();
if(root == null || root.left == null){
return -1;
}
TreeNode cur = root;
boolean flag = false;
int res = -1;
while(cur != null || !list.isEmpty()){
if(cur != null){
list.push(cur);
cur = cur.left;
}else{
cur = list.pop();
System.out.println(cur.val);
if(flag){
res = cur.val;
break;
}
if(cur.val == p){
flag = true;
}
cur = cur.right;
}
}
return res;
}
发表于 2015-09-30 15:35:15
回复(0)
中序遍历
import java.util.*;
/*
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}*/
public class Successor {
List<Integer> list=new ArrayList();
public int findSucc(TreeNode root, int p) {
// write code here
int a=-1;
trvise(root);
for(int i=0;i<list.size();i++){
if(p==list.get(i)&&i!=list.size()-1){
a=list.get(i+1);
}
}
return a;
}
public void trvise(TreeNode root){
if(root!=null){
trvise(root.left);
list.add(root.val);
trvise(root.right);
}
}
}
发表于 2018-04-02 10:18:56
回复(0)
思路
- 采用中序遍历的迭代算法，并记录上一个节点；
- 每次遍历一个节点时，判断上一个节点是否和目标节点相同；若相同，则返回当前节点即可。
代码
中序遍历是先访问左孩子、再访问根节点、最后访问右孩子； 由于要先访问左孩子，因此在迭代过程中需要记录根节点； 又因为最后访问的根节点在回溯时最先访问到，所以要将所有根节点记录在栈中。
- 首先创建一个栈 和 一个表示当前节点的指针，指向根节点；
-
当栈不为空 || 当前节点不为空 的时候就一直作如下循环：
- 若当前节点为空：则表示已经访问到左孩子的最底层，此时需要回溯；即从栈中取出一个根节点，访问它，再将当前节点指向该节点的右孩子
-
若当前节点不为空：则表示还没遍历到最左侧孩子的最底层；此时只需将当前节点入栈，并将当前节点指向左孩子即可。
public int findSucc(TreeNode root, int p) { if ( root==null ) return -1; Stack<TreeNode> stack = new Stack<>(); TreeNode curNode = root; int lastNode = root.val; while( curNode!=null || !stack.isEmpty() ){ if ( curNode==null ) { curNode = stack.pop(); if ( lastNode==p ) { return curNode.val; } lastNode = curNode.val; curNode = curNode.right; } else { stack.push( curNode ); curNode = curNode.left; } } return -1; }
发表于 2017-03-31 11:04:45
回复(0)
设置一个prev记录前一个节点的值，然后进行中序遍历，当prev=p时，当前节点就是值为p的节点的后继节点。
public class Successor {
public int findSucc(TreeNode root, int p) {
// write code here
int prev = -1;
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while(!stack.isEmpty() || root != null){
while(root != null){
stack.push(root);
root = root.left;
}
if(!stack.isEmpty()){
root = stack.pop();
if(prev == p) return root.val;
prev = root.val;
root = root.right;
}
}
return -1;
}
}
发表于 2021-11-25 22:55:22
回复(0)
第一次AC代码。先中序将值存入数组，遍历一次即可得到结果
第三次AC，递归改循环实现。
/*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};*/
class Successor {
public:
vector<int> q;
void dfs(TreeNode* root){
//中序
if(root==NULL){
return ;
}
dfs(root->left);
q.push_back(root->val);
dfs(root->right);
}
int findSucc(TreeNode* root, int p) {
// write code here
dfs(root);
for(int i=0;i<q.size();i++){
if(q[i]==p){
if(i==q.size()-1)return -1;
return q[i+1];
}
}
return -1;
}
}; 第二次AC 借鉴大佬的思路，在中序的过程中找到p值
/*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};*/
class Successor {
public:
int dfs(TreeNode* root,int p,bool &flag){
//中序
if(root==NULL){
return -1;
}
//先从左边找
int left=dfs(root->left,p,flag);
if(left!=-1){
//在左边找到了
return left;
}
if(flag==true){
//我的左儿子是p
return root->val;
}
if(root->val == p){
flag=true;
}
//左边没有找到的情况
return dfs(root->right,p,flag);
}
int findSucc(TreeNode* root, int p) {
// write code here
bool flag=false;
return dfs(root,p,flag);;
}
}; 第三次AC，递归改循环实现。
/*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};*/
class Successor {
public:
int findSucc(TreeNode* root, int p) {
// write code here
bool flag=false;
int result=-1;
stack<TreeNode*> s;
TreeNode* temp=root;
//递归改循环
while(temp!=NULL||!s.empty()){
if(temp!=NULL){
//一直往左边压栈
s.push(temp);
temp=temp->left;
}else{
//左儿子没有了
temp=s.top();
s.pop();
if(flag){
//p的后继
result=temp->val;
break;
}
if(temp->val==p){
//找到p值
flag=true;
}
//查看右儿子
temp=temp->right;
}
}
return result;
}
};
编辑于 2020-09-14 13:38:24
回复(0)
// 1\. 想到了要用中序遍历。
// 2\. 因此只需要一个prev节点。在每次visit(currNode)后，令prev = currNode，然后在这之前判断prev即可
class Successor {
public:
int findSucc(TreeNode* root, int p) {
// write code here
stack stackA;
TreeNode *scan = root;
TreeNode *prev = NULL;
while(stackA.size() || scan)
{
while(scan)
{
stackA.push(scan);
scan = scan->left;
}
scan = stackA.top();
stackA.pop();
// 如果有业务代码，这里会有visit(scan);
// 因为prev刚开始=NULL，所以这里的判断让其忽略第一次
if(prev && prev->val == p)
return scan->val;
prev = scan;
if(scan->right)
scan = scan->right;
else
scan = NULL;
}
return -1;
}
};
发表于 2020-05-23 17:19:31
回复(0)
class Successor {
public:
int findSucc(TreeNode* root, int p) {
stack<TreeNode*> s;
TreeNode* t = root;
bool flag = false;
while(!s.empty() || t){
if(t){
s.push(t);
t = t->left; }else{ t = s.top(); s.pop(); if(flag) return t->val; if(t->val == p) flag = true; t = t->right; } } return -1;
}
};
发表于 2019-02-26 02:00:33
回复(0)
中序遍历。设置一个标志位，用于标记是否找到了值为p的节点。
class Successor {
public:
bool flag = false;
int findSucc(TreeNode* root, int p) {
if (!root) { return -1; }
int a = findSucc(root->left, p);
if (-1 != a) { return a; }
if (flag) { return root->val; }
if (root->val == p) { flag = true; }
int b = findSucc(root->right, p);
if (-1 != b) { return b; }
return -1;
}
};
运行时间：6ms
占用内存：604k
发表于 2018-12-26 00:15:26
回复(0)
class Successor {
public:
bool flag=false;
void find(TreeNode* root,int p,int& last){
if(flag) return;
if(!root) return;
find(root->left,p,last);
if(last==p){ flag=true; last=root->val; return;}
if(!flag) last = root->val;
find(root->right,p,last);
}
int findSucc(TreeNode* root, int p) {
int last = p-1;
find(root,p,last);
if(flag) return last;
else return -1;
}
};
发表于 2017-08-24 21:26:01
回复(0)
//用队列来存
import java.util.*;
/*
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}*/
public class Successor {
Queue<Integer> queue=new LinkedList<Integer>();
public int findSucc(TreeNode root, int p) {
if(p<0||p>100000) return -1;
findSuccCore(root);
while(!queue.isEmpty()){
int temp=queue.poll();
if(temp==p&&(!queue.isEmpty()))
return queue.poll();
}
return -1;
}
public void findSuccCore(TreeNode root){
if(root==null) return;
findSuccCore(root.left);
queue.offer(root.val);
findSuccCore(root.right);
}
} Java程序员面试金典解题：http://blog.csdn.net/sinat_22797429/article/details/75451784
编辑于 2017-07-25 09:54:09
回复(0)
//方法一：直接中序遍历，简单粗暴
ArrayList<Integer> result=new ArrayList<Integer>();
public int findSucc(TreeNode root, int p) {
findSuccByCenterSort(root);
for(int i=0;i<result.size();i++) if(result.get(i)==p) return i==result.size()-1?-1:result.get(i+1);
return -1;
}
public void findSuccByCenterSort(TreeNode root) {
if(root==null) return;
if(root.left!=null) findSuccByCenterSort(root.left);
result.add(root.val);
if(root.right!=null)findSuccByCenterSort(root.right);
}
//方法二，同方法一，节省内存空间
boolean flag=false;
int result=-1;
public int findSucc(TreeNode root, int p) {
findSuccByCenterSort(root,p);
return result;
}
public void findSuccByCenterSort(TreeNode root,int p) {
if(root==null) return;
if(root.left!=null) findSuccByCenterSort(root.left,p);
if(flag) {
flag=false;
result=root.val;
}
if(root.val==p) flag=true;
if(root.right!=null)findSuccByCenterSort(root.right,p);
}
编辑于 2017-05-13 16:39:58
回复(0)
class Successor {
public:
bool isfind=false;
int findSucc(TreeNode* root, int p) {
if(root==0) return -1;
int left=findSucc(root->left,p);
if(left>-1) return left;
if(isfind) return root->val;
if(root->val==p) isfind=true;
int right=findSucc(root->right,p);
if(right>-1) return right;
return -1;
}
};
发表于 2016-08-13 21:08:34
回复(0)
//水货写个水程序，O(∩_∩)O哈哈~
class Successor {
public:
int findSucc(TreeNode* root, int p)
{
// write code here
vector<int> vec;
if(root==NULL || p<0) return -1;
helper(vec,root);
vec.push_back(-1);
int next=-1;
for(unsigned int i=0;i<vec.size();i++)
{
if(vec[i]==p)
{
next=vec[i+1];
}
}
return next;
}
void helper(vector<int>& vec,TreeNode* root)
{
if(root==NULL) return;
helper(vec,root->left);
vec.push_back(root->val);
helper(vec,root->right);
}
};
发表于 2016-08-07 11:26:29
回复(0)
思路：中序非递归遍历，找到相应那么下一个结点就是结果
# -*- coding:utf-8 -*-
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Successor:
def findSucc(self, root, p):
if not root:
return -1
stack = []
ph = root
isFind = False
result = -1
while ph or stack:
while ph:
stack.append(ph)
ph = ph.left
if stack:
top = stack.pop()
if isFind:
result = top.val
break
if top.val == p:
isFind = True
ph = top.right
return result
发表于 2016-08-03 15:04:30
回复(0)
//使用中序遍历，每次对遍历到的当前结点判断，如果val 为 p，则findFlag设置为真，下一个 //节点时，其值即为res,这个时候就可以将endFlag设置为真，也即无需继续遍历了 class Successor { public: int findSucc(TreeNode* root, int p) { bool findFlag = false, endFlag = false; int res = -1; searchBinary(root, p, findFlag, endFlag, res); return res; } void searchBinary(TreeNode* root, int p, bool &findFlag, bool &endFlag, int &res) { if(root->left != NULL) searchBinary(root->left, p, findFlag, endFlag, res); if(findFlag){ if(endFlag) return; endFlag = true; res = root->val; return; } if(root->val == p) findFlag = true; if(root->right != NULL) searchBinary(root->right, p, findFlag, endFlag, res); return; } };
发表于 2016-05-27 11:20:05
回复(0)
问题信息
难度：
111条回答
86收藏
16724浏览
通过挑战的用户
查看代码-
2022-09-13 13:49:11
-
2022-09-13 10:40:56
-
2022-09-06 08:19:38 -
2022-09-02 10:33:10
-
2022-09-01 21:47:00
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
