首页 > 试题广场 >

二叉树的下一个结点

[编程题]二叉树的下一个结点

热度指数：474902 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个二叉树其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的next指针。下图为一棵有9个节点的二叉树。树中从父节点指向子节点的指针用实线表示，从子节点指向父节点的用虚线表示

示例:

输入:{8,6,10,5,7,9,11},8

返回:9

解析:这个组装传入的子树根节点，其实就是整颗树，中序遍历{5,6,7,8,9,10,11}，根节点8的下一个节点就是9，应该返回{9,10,11}，后台只打印子树的下一个节点，所以只会打印9，如下图，其实都有指向左右孩子的指针，还有指向父节点的指针，下图没有画出来

数据范围：节点数满足 $1 \le n \le 50 \$ ，节点上的值满足 $1 \le val \le 100 \$

要求：空间复杂度 $O(1) \$ ，时间复杂度 $O(n)\$

输入描述:

输入分为2段，第一段是整体的二叉树，第二段是给定二叉树节点的值，后台会将这2个参数组装为一个二叉树局部的子树传入到函数GetNext里面，用户得到的输入只有一个子树根节点

输出描述:

返回传入的子树根节点的下一个节点，后台会打印输出这个节点

示例1

输入

{8,6,10,5,7,9,11},8

输出

示例2

输入

{8,6,10,5,7,9,11},6

输出

示例3

输入

{1,2,#,#,3,#,4},4

输出

示例4

输入

{5},5

输出

"null"

说明

不存在，后台打印"null"

说明：本题目包含复杂数据结构TreeLinkNode，点此查看相关信息

算法知识视频讲解

推荐

牛客304487号

分析二叉树的下一个节点，一共有以下情况：

1.二叉树为空，则返回空；

2.节点右孩子存在，则设置一个指针从该节点的右孩子出发，一直沿着指向左子结点的指针找到的叶子节点即为下一个节点；

3.节点不是根节点。如果该节点是其父节点的左孩子，则返回父节点；否则继续向上遍历其父节点的父节点，重复之前的判断，返回结果。代码如下：

class Solution {
public:
TreeLinkNode* GetNext(TreeLinkNode* pNode)
{
if(pNode==NULL)
return NULL;
if(pNode->right!=NULL)
{
pNode=pNode->right;
while(pNode->left!=NULL)
pNode=pNode->left;
return pNode;
}
while(pNode->next!=NULL)
{
TreeLinkNode *proot=pNode->next;
if(proot->left==pNode)
return proot;
pNode=pNode->next;
}
return NULL;
}
};

编辑于 2015-08-25 11:16:07 回复(49)

Java

apprentice_DYC

public class Solution {
    public TreeLinkNode GetNext(TreeLinkNode node) {
        // 如果右子树不为空就找右子树的最左节点
        if (node.right != null) {
            TreeLinkNode p = node.right;
            while (p.left != null) {
                p = p.left;
            }
            return p;
        }
        // 右子树为空就向上找第一个是其父节点"左孩子"的节点 ,该节点的父节点就是中序后继
        TreeLinkNode p = node;
        while (p.next != null) {
            if (p.next.left == p) {
                return p.next;
            }
            p = p.next;
        }
        // 找不到后继节点,说明是中序最后一个节点返回null
        return null;
    }
}

发表于 2025-06-22 23:56:01 回复(0)

Java

17c89

import java.util.*;
/*
public class TreeLinkNode {
    int val;
    TreeLinkNode left = null;
    TreeLinkNode right = null;
    TreeLinkNode next = null;

    TreeLinkNode(int val) {
        this.val = val;
    }
}
*/

/**
 * NC279 二叉树的下一个结点
 * @author d3y1
 */
public class Solution {
    public TreeLinkNode GetNext(TreeLinkNode pNode){
        // return solution1(pNode);
        return solution11(pNode);
        // return solution2(pNode);
    }

    private TreeLinkNode pre;
    private TreeLinkNode result;

    /**
     * 递归: 中序遍历
     * @param pNode
     * @return
     */
    private TreeLinkNode solution1(TreeLinkNode pNode){
        if(pNode == null){
            return null;
        }

        // 找到 根节点
        TreeLinkNode root = pNode;
        while(root.next != null){
            root = root.next;
        }

        inOrder(root, pNode);

        return result;
    }

    /**
     * 中序遍历
     * @param root
     * @param pNode
     */
    private void inOrder(TreeLinkNode root, TreeLinkNode pNode){
        if(result != null){
            return;
        }
        if(root == null){
            return;
        }

        inOrder(root.left, pNode);
        if(pre == null){
            pre = root;
        }else{
            if(pre.equals(pNode)){
                result = root;
                pre = root;
                return;
            }else{
                pre = root;
            }
        }
        inOrder(root.right, pNode);
    }

    /**
     * 递归: 中序遍历
     * @param pNode
     * @return
     */
    private TreeLinkNode solution11(TreeLinkNode pNode){
        if(pNode == null){
            return null;
        }

        // 找到 根节点
        TreeLinkNode root = pNode;
        while(root.next != null){
            root = root.next;
        }

        inorder(root, pNode);

        return result;
    }

    /**
     * 中序遍历
     * @param root
     * @param pNode
     */
    private void inorder(TreeLinkNode root, TreeLinkNode pNode){
        if(result != null){
            return;
        }
        if(root == null){
            return;
        }

        inorder(root.left, pNode);
        if(pre == pNode){
            result = root;
            pre = root;
            return;
        }else{
            pre = root;
        }
        inorder(root.right, pNode);
    }

    /**
     * 迭代: 分别考虑各种情况
     * @param pNode
     * @return
     */
    private TreeLinkNode solution2(TreeLinkNode pNode){
        if(pNode == null){
            return null;
        }

        // 有右子树
        if(pNode.right != null){
            pNode = pNode.right;
            while(pNode.left != null){
                pNode = pNode.left;
            }
            return pNode;
        }
        // 无右子树
        else{
            while(pNode.next != null){
                // 当前节点的父节点的左子节点 即是 当前节点
                if(pNode.next.left == pNode){
                    return pNode.next;
                }
                pNode = pNode.next;
            }
        }

        return null;
    }
}

发表于 2025-01-20 10:12:19 回复(0)

Java

kk1u

改进一下官方方法一，找到目标节点直接返回，不用遍历全部节点

public class Solution {
    private ArrayList<TreeLinkNode> path = new ArrayList<>();
    private TreeLinkNode ans = null;
    private TreeLinkNode pNode = null;

    public TreeLinkNode GetNext(TreeLinkNode pNode) {
        if(pNode == null){
            return null;
        }
        this.pNode = pNode;
        TreeLinkNode t = pNode;
        while(t.next!=null){
            t=t.next;
        }
        TreeLinkNode root = t;
        midOrder(root);
        return ans;
    }

    public void midOrder(TreeLinkNode root){
        if(root==null || ans!=null){
            return;
        }
        midOrder(root.left);
        if(ans!=null){
            return;
        }
        path.add(root);
        if(ans == null && path.size()>1 && path.get(path.size()-2).equals(this.pNode)){
            ans = path.get(path.size()-1);
        }
        midOrder(root.right);
    }
}

发表于 2024-12-02 11:28:13 回复(0)

Java

牛客305469798号

import java.util.*;
public class Solution {
    public TreeLinkNode GetNext(TreeLinkNode pNode) {
        TreeLinkNode ans = pNode;
        while (ans.next != null) {
            ans = ans.next;
        }
        if (pNode.left == null && pNode.right == null && pNode.next == null) {
            return null;
        }
        if (findRight(ans) == pNode) {
            return null;
        }
        if (pNode.right == null) {
            if (pNode == pNode.next.left) {
                return pNode.next;
            }
            while (pNode != pNode.next.left) {
                pNode = pNode.next;
            }
            return pNode.next;
        }
        return findLeft(pNode.right);
    }
    public TreeLinkNode findRight(TreeLinkNode pNode) {
        while (true) {
            if ((pNode.right == null)) {
                return pNode;
            }
            pNode = pNode.right;
        }
    }
    public TreeLinkNode findLeft(TreeLinkNode pNode) {
        while (true) {
            if ((pNode.left == null)) {
                return pNode;
            }
            pNode = pNode.left;
        }
    }
}

发表于 2024-06-11 23:39:18 回复(0)

Java

有力量的王老五年薪百万

public class Solution {

public TreeLinkNode GetNext(TreeLinkNode pNode) {

if (pNode == null) return null;

if (pNode.right != null) {

TreeLinkNode pNodeRight = pNode.right;

while (pNodeRight.left != null) {

pNodeRight = pNodeRight.left;

}

return pNodeRight;

}

if (pNode.next != null && pNode.next.left == pNode) {

return pNode.next;

}

while (pNode.next != null && pNode.next.right == pNode) {

pNode = pNode.next;

}

return pNode.next;

}

编辑于 2024-03-10 12:49:37 回复(0)

Java

帅气的小熊猫在学习

分类讨论

import java.util.*;
/*
public class TreeLinkNode {
    int val;
    TreeLinkNode left = null;
    TreeLinkNode right = null;
    TreeLinkNode next = null;

    TreeLinkNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {
    public TreeLinkNode GetNext(TreeLinkNode pNode) {
        // 二叉树结构题
        // 中序遍历下某节点的下一个节点分为以下情况
        // 1.该节点没有右孩子，且该节点是其父节点的左孩子，那么他的父节点便是下一个节点
        // 2.该节点没有右孩子，且该节点是其父节点的右孩子，那么迭代从他的父亲节点开始，
        // 一直到节点是其父亲节点的左孩子，回到1的情况
        // 3.该节点有右孩子，那么右孩子最左端的节点是下一个节点
        if (pNode.right == null) { // 情况1、2
            while (pNode.next != null && pNode.next.left != pNode) { // 情况2
                pNode = pNode.next;
            }
            return pNode.next;
        }
        pNode = pNode.right; // 情况3
        while (pNode.left != null) {
            pNode = pNode.left;
        }
        return pNode;
    }
}

发表于 2023-07-18 11:04:28 回复(0)

Java

Juliuszzz

分三种情况分别处理

public class Solution {
    public TreeLinkNode GetNext(TreeLinkNode pNode) {
        //还有右子树，就找到右子树的最左侧叶子结点
        if(pNode.right!=null) {
            TreeLinkNode node = pNode.right;
            while(node.left!=null) node=node.left;
            return node;
        }
        //没有右子树，判断自己是左儿子还是右儿子
        //是左儿子
        else if(pNode.next != null && pNode == pNode.next.left)   return pNode.next;
        while(pNode.next != null){
            //是右儿子，则一直往上找父亲节点，直到是左儿子
            if(pNode == pNode.next.right)
                pNode = pNode.next;
            else return pNode.next;
        } 
        //是根节点且没有右子树
        return null;
    }
}

发表于 2023-03-18 00:59:28 回复(0)

Java

小鳖

public class Solution {
    public TreeLinkNode GetNext(TreeLinkNode pNode) {
        return pNode.right == null ? toUp(pNode) : toRight(pNode.right);
    }

    TreeLinkNode toRight(TreeLinkNode node) {
        if (node.left == null) return node;
        return toRight(node.left);
    }

    TreeLinkNode toUp(TreeLinkNode node) {
        if (node.next == null) return null;
        if (node == node.next.left) return node.next;
        return toUp(node.next);
    }
}

发表于 2023-02-01 13:29:15 回复(0)

Java

two倩

1、直接中序遍历

import java.util.*; public class Solution { public void Inorder(TreeLinkNode head,List<TreeLinkNode> list){ if(head==null) return ;  Inorder(head.left,list);  list.add(head);  Inorder(head.right,list);  } public TreeLinkNode GetNext(TreeLinkNode pNode) {
        List<TreeLinkNode> list=new ArrayList<>();  TreeLinkNode cur=pNode;//pNode是要查找的结点  while(cur.next!=null)//要获取到父节点  cur=cur.next;  Inorder(cur,list);  for(int i=0;i<list.size()-1;i++){ if(list.get(i)==pNode) return list.get(i+1);  } return null;  }
}

时间复杂度：遍历结点O（N），空间复杂度：链表存储每一结点O（N）

2、根据中序遍历的特点

import java.util.*;
/*
public class TreeLinkNode {
int val;
TreeLinkNode left = null;
TreeLinkNode right = null;
TreeLinkNode next = null;

TreeLinkNode(int val) {
this.val = val;
}
}
*/
public class Solution {
public TreeLinkNode GetNext(TreeLinkNode pNode) {
if(pNode==null)
return null;
//1、如果有右子树，下一个结点是右子树最左侧的结点
if(pNode.right!=null){
pNode=pNode.right;//右子树的根节点
while(pNode.left!=null){
pNode=pNode.left;
}
//pNode是左子树的叶子节点
return pNode;
}
//2、如果没有右子树并且是父节点的左节点，那么下一个结点就是父节点

TreeLinkNode parent=pNode.next;//得到父节点
if(parent!=null&&parent.left==parent){
return parent;
}
//3、如果没有右子树并且是父节点的右子树上的结点，那么下一个结点就是所在右子树的根节点的父节点

//这里，只有一个右子树中序遍历的最后一个结点（也就是右子树中序序列的最后一个结点）的下一个结点才会是所在右子树的根节点的父节点；这个右子树的根节点一定会是它的父节点的左节点；因为中序序列的最后一个结点在整个树的左子树，才会有下一个结点，如果在整个树的右子树，是不会有下一个节点的

b c

对于c，他也是a所在右节点的中序遍历的最后一个结点，也是整个树中序序列的末尾是不会有最后一个结点的

while(parent!=null){
if(parent.left==pNode)
return parent;
parent=parent.next;
pNode=pNode.next;
}
return null;
}
}

发表于 2022-08-25 14:16:16 回复(0)

Java

阿杆

public class Solution {
    TreeLinkNode target = null;
    boolean ready = false;
    int val;

    public TreeLinkNode GetNext(TreeLinkNode pNode) {
        this.val = pNode.val;
        while (pNode.next != null) {
            pNode = pNode.next;
        }
        dfs(pNode);
        return target;
    }

    private void dfs(TreeLinkNode node) {
        if (node.left != null) {
            dfs(node.left);
        }
        if (ready) {
            target = node;
            ready = false; 
            return ;
        }
        if (node.val == val){
            ready = true;
        }
        if (node.right != null) {
            dfs(node.right);
        }
    }
}

发表于 2022-07-23 11:56:06 回复(0)

Java

勇敢牛牛不怕难

import java.util.*;
/*
public class TreeLinkNode {
    int val;
    TreeLinkNode left = null;
    TreeLinkNode right = null;
    TreeLinkNode next = null;

    TreeLinkNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {
    public TreeLinkNode GetNext(TreeLinkNode pNode) {
        if(pNode==null){
            return null;
        }
        if(pNode.right!=null){
            return fun(pNode.right);
        }
        if(pNode.next==null){
            return null;
        }
        if(pNode.next.left==pNode){
            return pNode.next;
        } 
        
        return fun2(pNode.next);
    }
    
     //找父节点
    public TreeLinkNode fun2(TreeLinkNode node){
        if(node.next==null){
            return null;
        }
        if(node.next.right==node){
            return fun2(node.next);
        }
        return node.next;
    }
    
        
    //找左节点
    public TreeLinkNode fun(TreeLinkNode node){
        if(node.left==null){
            return node;
        }
        return fun(node.left);
    }
}

发表于 2022-06-30 22:56:42 回复(0)

Java

西柚小白

分情况
一、当前节点有右节点，向下找，返回右子树的最左节点
二、当前节点没有右节点，向上找。直到找到「其左儿子是当前节点」的父节点

三、根据以上方法还没找到下一节点，说明当前节点就是整棵树中序遍历的最后一个节点，返回null。

代码如下：

    public TreeLinkNode GetNext(TreeLinkNode pNode) {
        //往下找
        if(pNode.right != null){
            pNode = pNode.right;//从右子树的根节点开始查找
            while (pNode.left != null){
                pNode = pNode.left;
            }
            return pNode;
        }

        //往上找
        while (pNode.next != null){
            if(pNode.next.left == pNode){
                return pNode.next;
            }
            pNode = pNode.next;
        }
        return null;
    }

发表于 2022-04-01 11:41:29 回复(0)

Java

不吃肉的兔子

/*
public class TreeLinkNode {
    int val;
    TreeLinkNode left = null;
    TreeLinkNode right = null;
    TreeLinkNode next = null;

    TreeLinkNode(int val) {
        this.val = val;
    }
}
*/
import java.util.*;
public class Solution {
    public TreeLinkNode GetNext(TreeLinkNode pNode) {
        ArrayList<TreeLinkNode> list = new ArrayList<>();
        TreeLinkNode node = pNode;
        while(node.next != null){
            node = node.next;
        }
        Inorder(node,list);
        for(int i=0;i<list.size();i++){
            if(pNode == list.get(i)){
                return i==list.size()-1?null:list.get(i+1);
            }
        }
        return null;
    }
    public void Inorder(TreeLinkNode root,ArrayList<TreeLinkNode> list){
        if(root == null) return;
        Inorder(root.left,list);
        list.add(root);
        Inorder(root.right,list);
    }
}

发表于 2022-03-24 16:03:15 回复(0)

Java

624huiguorou

把给的测试用例画出来

1.当所求结点有右子树时，下一个结点为该节点右结点最左边的结点

2.当所求结点没有右子树时，(1)如果它是父节点的左节点，那么它下一个结点就是该父节点

(2)它是父节点的右节点，那么就往上找父节点，直到该父节点是父节点本身的父节点的左节点，那么下一个结点就是这个找到的父节点的父节点。

注意pNode.next为null的情况，与根节点联系起来，根节点没有右子树时它就是最后一个结点。

[8,10]作为测试用例可以方便验证。

public class Solution {
    public TreeLinkNode GetNext(TreeLinkNode pNode) {
        TreeLinkNode p = null;
        //所求结点有右子树
        if(pNode.right != null){
            p = pNode.right;
            while(p.left != null){
                p = p.left;
            }
            return p;
        }
        //没有右子树且没有父节点，此时为根节点，为终点，返回null
        if(pNode.next == null){
            return null;
        }
        //所求结点没有右子树
        if(pNode == pNode.next.left){
            return pNode.next;
        }else{
            p = pNode.next;
            while(p.next != null && p != p.next.left){
                p = p.next;
            }
            if(p.next != null){
                return p.next;
            }
        }
        return null;
    }
}

发表于 2022-03-23 17:14:35 回复(0)

Java

图南qqqq

/*
public class TreeLinkNode {
    int val;
    TreeLinkNode left = null;
    TreeLinkNode right = null;
    TreeLinkNode next = null;

    TreeLinkNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {
    public TreeLinkNode GetNext(TreeLinkNode pNode) {
        //has right child
        if (pNode.right!=null){
            TreeLinkNode tmp = pNode.right;
            while(tmp.left!=null){
                tmp = tmp.left;
            }
            return tmp;
        }
        //no right child and is root
        if (pNode.next==null) return null;
        //no rightchild and is leftchild of parent
        if (pNode.right==null && pNode.next.left==pNode){
            return pNode.next;
        }
        //no rightchild and is rightchild of parent
        if (pNode.right==null && pNode.next.right==pNode){
            TreeLinkNode parent = pNode.next;
            while(parent.next!=null){
                if (parent.next.left == parent) return parent.next;
                parent = parent.next;
            }
            return null;
        }
        return null;
    }
}

发表于 2022-03-16 11:48:31 回复(0)

Java

pentAstro

/*
public class TreeLinkNode {
int val;
TreeLinkNode left = null;
TreeLinkNode right = null;
TreeLinkNode next = null;

TreeLinkNode(int val) {
this.val = val;
}
}
*/
// 思路：中序遍历，找到这个节点的下一个节点，首先要找到这个节点
// 中序遍历得用递归或者栈实现, 用递归实现后发现那个条件无法判断
// ** 重点不是要实现中序遍历，而是要根据中序遍历的思想设计判断条件

// 可以从中序遍历的思想入手设计判断条件
// 1. 若该节点有右节点, 则输出右子树的最左孩子
// 2. 若该节点无右节点，则看该节点是否是其父节点的左孩子，若是，输出其父节点
// 3. 若该节点无右节点, 则顺着该结点回溯，知道找到一个节点是其父节点的左孩子，输出其父节点
public class Solution {
int inputNum;
TreeLinkNode result;
public TreeLinkNode GetNext(TreeLinkNode pNode) {
if(pNode.right != null) { // 1. 若该节点有右节点, 则输出右子树的最左孩子
pNode = pNode.right;
while(pNode.left != null) { // 找到右子树的最左孩子
pNode = pNode.left;
}
return pNode;
} else{
if(pNode.next != null){ // 若该节点有父节点，则进入 2 和 3 的判断
while(pNode.next != null){ // 沿着该节点的父节点回溯
if(pNode.next.left == pNode) { // 只要找到一个节点是其父节点的左节点就返回
return pNode.next;
} else {
pNode = pNode.next;
}
}
return null;
} else {
return null;
}
}
}

}

发表于 2022-03-12 15:59:30 回复(0)

Java

牛客683289936号

public class Solution {
   TreeLinkNode pre = null; 
    TreeLinkNode head = null;
    public TreeLinkNode GetNext(TreeLinkNode pNode) {
            TreeLinkNode root = pNode;
        
            while(root.next!=null){
                root = root.next;
            }//找到整棵树的根节点
    
            dfs(root);//从根节点中序遍历构造链表
            
            pre.next = null; //此时pre刚好是最后一个，最后一个的next设置为null

           return pNode.next;
        
    }
    
    public void dfs(TreeLinkNode root){
        if(root==null) return;
        dfs(root.left);
        if(pre!=null){
          pre.next = root;
        }else{
          head = root;
        }
        pre = root;
        dfs(root.right);
    }
}

发表于 2022-03-02 10:52:50 回复(0)

提交观点

问题信息

树

难度：

148条回答 2627收藏 112665浏览

通过挑战的用户

查看代码

阿絮吖吖_

2023-03-11 16:20:59
牛客44839...

2023-03-07 00:26:12
牛客唯一真0o...

2023-03-05 12:34:00
会有offer...

2023-02-24 16:52:16
求实习的啤酒肚很热血

2023-02-21 10:42:32

二叉树的下一个结点

输入描述:

输出描述:

输入

输出

输入

输出

输入

输出

输入

输出

说明

说明：本题目包含复杂数据结构TreeLinkNode，点此查看相关信息

问题信息

热门推荐

通过挑战的用户

相关试题