首页 > 试题广场 >

二叉树的下一个结点

[编程题]二叉树的下一个结点
  • 热度指数:465191 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 64M,其他语言128M
  • 算法知识视频讲解
给定一个二叉树其中的一个结点,请找出中序遍历顺序的下一个结点并且返回。注意,树中的结点不仅包含左右子结点,同时包含指向父结点的next指针。下图为一棵有9个节点的二叉树。树中从父节点指向子节点的指针用实线表示,从子节点指向父节点的用虚线表示

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

要求:空间复杂度 ,时间复杂度

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


输出描述:
返回传入的子树根节点的下一个节点,后台会打印输出这个节点
示例1

输入

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

输出

9
示例2

输入

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

输出

7
示例3

输入

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

输出

1
示例4

输入

{5},5

输出

"null"

说明

不存在,后台打印"null"   

说明:本题目包含复杂数据结构TreeLinkNode,点此查看相关信息
推荐
分析二叉树的下一个节点,一共有以下情况:
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)
/*
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;
        
        TreeLinkNode pNext = null;
        //如果当前节点有右叶子节点,我们就寻找当前节点的右子树种最左边的那个点
        if(pNode.right!=null){
            TreeLinkNode pRight = pNode.right;
            while(pRight.left!=null)
                pRight = pRight.left;
            pNext = pRight;
        }
        //如果当前节点没有右叶子节点,则应当向上寻找当前节点的父节点中属于祖父节点的左子节点的那一个
        else if(pNode.next!=null){
            TreeLinkNode pCurrent = pNode;
            TreeLinkNode pParent = pNode.next;
            while(pParent!=null && pCurrent!=pParent.left){
                pCurrent = pParent;
                pParent = pParent.next;
            }
            pNext = pParent;
        }
        //否则返回null-
        return pNext;
    }
}

发表于 2017-08-02 15:11:34 回复(0)
/*
因为中序遍历遵循LVR的顺序,其中L为左子树,V为节点值,R为右子树。
根据所给节点与其他节点的关系,分类讨论:
1>所给节点如果有右孩子,则直接返回右孩子;
2>否则,如果所给节点没有父节点,当前节点为没有右子树的根节点,返回NULL;
3>否则,如果所给节点为父节点的左孩子,直接返回父节点;
4>否则,沿父节点向上,直到找到一个节点x,满足:
    pNode位于x节点的左子树 && pNode位于x左孩子的右子树
    返回x节点。
*/
class Solution {
public:
    TreeLinkNode* GetNext(TreeLinkNode* pNode)
    {
        if (pNode == NULL)  
            return NULL;
        TreeLinkNode *p = pNode;
        TreeLinkNode *ret = NULL;
        if (p->right)  //当前节点存在右孩子
        {
            p = p->right;
            while (p->left)
                p = p->left;
            ret = p;
        }
        else if (p->next == NULL)  //当前节点没有父节点和右孩子
            ret = NULL;
        else 
        {
            if (p == p->next->left)  //当前节点为其父节点的左孩子
                ret = p->next;
            else              //当前节点为父节点的右孩子
            {
                TreeLinkNode *par = p->next;
                while (par)   //沿父节点上溯
                {
                    if (par->next == NULL)
                        break;
                    else if (par == par->next->right)
                        par = par->next;
                    else
                        break;
                }
                ret = par->next;
            }
        }
        return ret;
    }
};

编辑于 2017-07-31 12:05:20 回复(4)
public class Solution {
    TreeLinkNode GetNext(TreeLinkNode node)
    {
        if(node==null) return null;
        if(node.right!=null){    //如果有右子树,则找右子树的最左节点
            node = node.right;
            while(node.left!=null) node = node.left;
            return node;
        }
        while(node.next!=null){ //没右子树,则找第一个当前节点是父节点左孩子的节点
            if(node.next.left==node) return node.next;
            node = node.next;
        }
        return null;   //退到了根节点仍没找到,则返回null
    }
}

发表于 2015-06-15 16:34:40 回复(38)

思路:首先知道中序遍历的规则是:左根右,然后作图


结合图,我们可发现分成两大类:1、有右子树的,那么下个结点就是右子树最左边的点;(eg:D,B,E,A,C,G) 2、没有右子树的,也可以分成两类,a)是父节点左孩子(eg:N,I,L) ,那么父节点就是下一个节点 ; b)是父节点的右孩子(eg:H,J,K,M)找他的父节点的父节点的父节点...直到当前结点是其父节点的左孩子位置。如果没有eg:M,那么他就是尾节点。
/*
struct TreeLinkNode {
int val;
struct TreeLinkNode *left;
struct TreeLinkNode *right;
struct TreeLinkNode *next;
TreeLinkNode(int x) :val(x), left(NULL), right(NULL), next(NULL) {
}
};
*/
//分析二叉树的下一个节点,一共有以下情况:
//1.二叉树为空,则返回空;
//2.节点右孩子存在,则设置一个指针从该节点的右孩子出发,一直沿着指向左子结点的指针找到的叶子节点即为下一个节点;
//3.节点不是根节点。如果该节点是其父节点的左孩子,则返回父节点;否则继续向上遍历其父节点的父节点,重复之前的判断,返回结果。
classSolution{
public:
    TreeLinkNode* GetNext(TreeLinkNode* pNode)
    {
        if (pNode == NULL)
            returnNULL;
        if (pNode->right != NULL)
        {
            pNode = pNode->right;
            while (pNode->left != NULL)
                pNode = pNode->left;
            returnpNode;
        }
        while (pNode->next != NULL)
        {
            TreeLinkNode *proot = pNode->next;
            if (proot->left == pNode)
                returnproot;
            pNode = pNode->next;
        }
        returnNULL;
    }
};

编辑于 2018-01-02 15:14:29 回复(41)
思路:
    //当前结点为根结点时:
    //1)若根结点无右子树,返回NULL
    //2)若根结点有右子树,返回右子树中最左端的结点
    
    //当前结点为左叶子结点:
    //直接返回其父结点
   
    //当前结点为右叶子结点
    //1)若其祖父结点存在且其父结点是其祖父结点的左结点,返回其祖父结点
    //2)否则,返回NULL
   
    //当前结点为非叶子结点
    //1)若无右子树,返回其父结点
    //2)若有右子树,返回其右子树中最左端的结点
    
发表于 2015-05-04 11:41:16 回复(1)
/*
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) {
        // 时间复杂度O(N),空间复杂度O(1)
        if (pNode == nullptr) return nullptr;
        TreeLinkNode *res = nullptr;
        if (pNode->right) {
            res = pNode->right;
            while (res->left) res = res->left;
        } else {
            res = pNode->next;
            if (res == nullptr) return res;
            while (res->left != pNode) {
                pNode = res;
                res = pNode->next;
                if (res == nullptr) return res;
            }
        }
        return res;
    }
};

发表于 2022-08-10 20:13:27 回复(0)

由于求的是中序遍历序列下下一个节点的值,所以需要着重关注一下中序遍历序列

  • 首先看一下当前节点是否存在右子树
    • 存在的话,那么右子树的最左侧的节点便是下一个将要遍历的节点(这里的代码自己需要注意一下写法)
    • 不存在的话,那么当前节点是否位于父节点的左侧?
      • 是的话,那么父节点便是下一个将要遍历的节点。
      • 否的话,那么沿着父节点向上找。直到找到第一个,使得整个分支都位于该节点的左侧,那么这个节点便是下一个将要遍历的节点。找不到则返回nullptr
class Solution {
public:
    TreeLinkNode* GetNext(TreeLinkNode* pNode) {
        //判断是否为空
        if(!pNode) return nullptr;
        TreeLinkNode* pNext = nullptr;
        //若当前节点的右子树非空
        if(pNode -> right){
            TreeLinkNode* pRight = pNode -> right;
            while(pRight -> left) pRight = pRight -> left;
            pNext = pRight;
        }
        //当前节点的右子树的空的,但是父节点非空
        else if(pNode -> next){
            TreeLinkNode* pCurrent = pNode;
            TreeLinkNode* pParent = pNode -> next;
            while(pParent && pCurrent == pParent -> right){
                pCurrent = pParent;
                pParent = pParent -> next;
            }
            pNext = pParent;
        }
        
        return pNext;
    }
};


发表于 2022-01-21 21:34:16 回复(0)
我觉得最容易理解的思路,翻了半天没人这样做。
1、找到根节点
2、输出中序遍历
3、找到给定节点的下一个节点

/*
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:
    vector<TreeLinkNode*> vec;
    void order(TreeLinkNode* pRootOfTree){
        if(!pRootOfTree) return;
        order(pRootOfTree->left);
        vec.push_back(pRootOfTree);
        order(pRootOfTree->right);
    }
    TreeLinkNode* GetNext(TreeLinkNode* pNode) {
        if(!pNode) return NULL;
        TreeLinkNode* temp = pNode;
        TreeLinkNode* res = NULL;
        while(temp->next){
            temp = temp->next;
        }
        order(temp);
        for(int i = 0;i < vec.size() - 1;i++){
            if(vec[i] == pNode) res = vec[i + 1];
        }
        return res;
        
    }
};


发表于 2021-12-27 01:10:34 回复(0)
public class Solution {
    public TreeLinkNode GetNext(TreeLinkNode pNode) {
        TreeLinkNode ret = pNode;
        if (pNode.right!=null) ret=GetLeft(pNode.right);
        else ret=CheckNextisLeft(pNode);
        return ret;
    }
    TreeLinkNode GetLeft(TreeLinkNode p){
        TreeLinkNode ret = p;
        if(p.left!=null)ret = GetLeft(p.left);
        return ret;
    }
    TreeLinkNode CheckNextisLeft(TreeLinkNode p){
        if(p.next==null)return null;
        if(p.next.left==p)return p.next;
        TreeLinkNode ret = CheckNextisLeft(p.next);
        return ret;
    }
}
Java 递归解法
发表于 2021-11-09 19:13:07 回复(0)
/*function TreeLinkNode(x){
    this.val = x;
    this.left = null;
    this.right = null;
    this.next = null;
}*/
//暴力解法
let mydata=[]
function GetNext(pNode)
{    
    //传入的第一个节点就是我们要求的节点的父节点 而并不是树的真正根节点
    let firstnode=pNode
    //保存传入的节点
    let temp=pNode
    //递归父树直到根节点 
    while(temp.next!=null){
        temp=temp.next
    }
    //传入真正的根节点 中序遍历保存结果
    getmydata(temp)
    //保存要返回的结果
    let finaldata=null
    //遍历中序树的数组
    mydata.forEach((v,i)=>{
        if(v==firstnode){
                       //返回要求节点的下一个节点 
           finaldata= mydata[i+1]
        }
    })
    
    return finaldata
}
//中序遍历
function getmydata(pNode){
    if(!pNode) return 
    getmydata(pNode.left)
    mydata.push(pNode)
    getmydata(pNode.right)
}

module.exports = {
    GetNext : GetNext
};

发表于 2021-09-13 20:42:46 回复(0)
function GetNext(pNode)
{
    // write code here
    //1.如果一个节点有右子树,那么它的下一个节点就是它的右子树中的最左子节点。也就是说,从右子节点出发一直沿着指向左子节点的指针,我们就能找到下一个节点。

    //2.如果没有右子树,又可以分为两种情况
        //1)如果节点是它父节点的左子节点,那么它的下一个节点就是它的父节点。
        //2)如果一个节点既没有右子树,并且它还是父节点的右子节点,那么需要沿着指向父节点的指针一直向上便利,直到找到一个是它父节点的左子节点的节点。
    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) {
        if(pNode == pNode.next.left) {
            return pNode.next;
        }
        pNode = pNode.next;
    }
    return null;
}

发表于 2021-04-05 12:49:47 回复(0)

二叉树的下一个结点-根据中序遍历的特点(O(n),O(1))解题

    //解题思路
    /*
           8
        6    10
       5 7  9  11
    根据中序遍历的特点(O(n),O(1)):
    1.pNode的右孩子为空,中序遍历顺序的下一个结点可能在其父辈root里(注意是父辈,不只是父亲)
        1.1 pNode为root的左孩子,则pNode的下一个结点为root(例如5、7、9)
        1.2 否则返回null(例如11)
    2.pNode的右孩子不为空时,中序遍历顺序的下一个结点在其右子树里,此时中序遍历右子树取第一个结果即可(例如6、8、10)
     */
    //犯错点
    /*
      求中序遍历右子树取第一个结果即取右子树最左边的节点,不用调用inOrder()耗费运行时间
     */
    public TreeLinkNode GetNext(TreeLinkNode pNode) {
        if (pNode == null) return null;
        //1.pNode的右孩子为空,中序遍历顺序的下一个结点可能在其父辈里
        if (pNode.right == null){
            TreeLinkNode root = pNode.next;
            TreeLinkNode child = pNode;
            //1.1 pNode为root父辈的左孩子,则pNode的下一个结点为root
            while (root != null){
                if (root.left == child) return root;
                child = root;
                root = root.next;
            }
            //1.2 父辈root为空,则返回null
            return null;
        }
        //2.pNode的右孩子不为空,中序遍历顺序的下一个结点在其右子树里,此时中序遍历右子树取第一个结果即可
        TreeLinkNode rightTree = pNode.right;
        //求中序遍历右子树取第一个结果即取右子树最左边的节点
        while (rightTree.left != null){
            rightTree = rightTree.left;
        }
        return rightTree;
    }

发表于 2021-03-19 22:08:08 回复(0)

思路

这道题就不多说了,难度不高,在草纸上分析好每种情况就行,稍微注意一下代码优化,简洁一些。

代码

    /**
     * 3种情况:
     * 1.pNode有右结点 找右结点开始最左边的
     * 2.pNode无右,且是父结点next的左结点 则父结点就是中序的下一个
     * 3.pNode无右,且是父结点的右节点 找父结点直到有“右父结点”(即它是父结点的左子结点)为止
     */
    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 && pNode.next.right == pNode) pNode = pNode.next;
        return pNode.next;
    }
发表于 2021-02-04 12:24:04 回复(0)
import java.util.ArrayList;
import java.util.List;
/**
 * 1.找到根节点
 * 2.将二叉树每个结点按中序遍历顺序存到数组中
 * 3.获取当前结点在数组中的索引
 * 4.返回索引+1所指的结点
 * @author YueTsao
 *
 */
public class Solution {
	List<TreeLinkNode> list = new ArrayList<>();
	public TreeLinkNode GetNext(TreeLinkNode pNode){
		TreeLinkNode pRoot = pNode;
		//找到根节点
		while(pRoot.next!=null)
			pRoot = pRoot.next;
		Mark(pRoot);
		int index = list.indexOf(pNode);
		//若为数组中最后一个元素则返回空
		if(index==list.size()-1)
			return null;
		else
			return list.get(index+1);
    }
	/**
	 * 通过递归将二叉树每个结点按中序遍历顺序存到数组中
	 * @param pRoot 
	 */
	public void Mark(TreeLinkNode pRoot) {
		if(pRoot!=null) {
			Mark(pRoot.left);
			list.add(pRoot);
			Mark(pRoot.right);
		}
	}
}

发表于 2020-07-25 20:43:20 回复(0)
class Solution {
public:
	vector<TreeLinkNode* > result;
	TreeLinkNode* GetNext(TreeLinkNode* pNode)
	{
		//TreeLinkNode* & rp = pNode;
		TreeLinkNode*  root= pNode;
		while (root->next != NULL) {
			root = root->next;
		}
		inorder(root);
		int i = 0;
		while (1) {
			if (result.at(i) == pNode) {
				//如果所给点是中序遍历最后一个则返回空
				if (i == result.size() - 1) {
					return NULL;
				}
				else {
					return result.at(i + 1);
				}
			}
			++i;
		}
	}
	//中序遍历
	void inorder(TreeLinkNode* &node) {
		if (node == NULL) {
			return;
		}
		if (node->left != NULL) {
			inorder(node->left);
		}
		result.push_back(node);
		if (node->right != NULL) {
			inorder(node->right);
		}
	}
};
简单易懂的思路。。。把中序序列录入数组,然后直接找,如果是最后一个节点,则直接返回空
发表于 2020-07-19 08:59:06 回复(0)
function GetNext(pNode)
{
    // write code here
    if(!pNode){
        return pNode
    }
    if(pNode.right){
        pNode = pNode.right
        while(pNode.left){
            pNode = pNode.left
        }
        return pNode
    }
    while(pNode.next){
        if(pNode === pNode.next.right){
            pNode = pNode.next
        }else{
            return pNode.next
        }
        
    }
    return null
思路:
1.考虑basecase
2.如果给定的节点有右子节点,就向给定节点的右子树遍历,并且让
pNode = pNode.right
遍历pNode的左子树直到pNode.left为空,则此pNode为所求
3..如果给定的节点(pNode)没有右子节点,就向给定节点的父亲遍历,并判断pNode是否为其父亲的右子节点,若为真,则令
 pNode = pNode.next
直到pNode为其父亲的左子节点,则pNode的父亲为所求。若pNode的父亲为空,则退出循环返回null,就是下图中I节点
发表于 2020-07-09 22:07:41 回复(0)
//分享一个递归的解法
class Solution {
public:
    bool find=false;
    TreeLinkNode* ans=NULL;
    TreeLinkNode* GetNext(TreeLinkNode* pNode)
    {//有右子树中序遍历找右子树 无右子树找左父节点
        if(pNode==NULL) return NULL;
        if(pNode->right!=NULL) InOrder(pNode->right);//不能包含本身
        else find_father(pNode);
         
        return ans;
    }
     
    void InOrder(TreeLinkNode* r)
    {
        if(r==NULL||find) return;
        InOrder(r->left);
        if(!find){
            find=true;
            ans=r;   
        }
        InOrder(r->right);  
    }
    
    void find_father(TreeLinkNode* r)
    {
        if(!r->next||find) return;
        if(r->next->left==r){
            find=true;
            ans=r->next;
        }
        find_father(r->next);
    }
};

发表于 2020-06-28 10:59:50 回复(0)
# -*- coding:utf-8 -*-
# class TreeLinkNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#         self.next = None
class Solution:
    def GetNext(self, pNode):
        # write code here
        #有右子树
        if pNode.right:
            p = pNode.right
            while p.left:
                p = p.left
            return p
        #无右子树
        while pNode.next:
            if pNode.next.left == pNode:    #如果,该节点是父节点的左节点,则父节点为该节点的下一个节点
                return pNode.next
            else:
                pNode = pNode.next    #该节点是父节点的右节点,不满足条件,继续向上寻找父节点。
        return

编辑于 2020-06-12 22:09:55 回复(1)
借鉴各位大佬的思路;主要有借助三个:一是借助指向父节点的指针使之指向树的顶点;二是使用中序遍历,当中使用线性表存储即为三;最后判断返回节点在线性表中的下一个节点;
/*
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 {
    static ArrayList<TreeLinkNode> list =  new ArrayList<>();
    public TreeLinkNode GetNext(TreeLinkNode pNode)
    {
        //是否为空
        if(pNode==null) return null;
        //指向父节点,获得顶父节点;
        TreeLinkNode pa = pNode;
        while(pNode.next!=null){
            pNode = pNode.next;
        }
        //中序遍历并存在list中;
        inOrder(pNode);
        for(int i=0;i<list.size();i++){
            if(pa==list.get(i)){
                return pa =i==(list.size()-1)?null:list.get(i+1);
            }
        }
        return null;
    }
    public void inOrder(TreeLinkNode pNode){
        if(pNode==null) return;
        inOrder(pNode.left);
        list.add(pNode);//存储节点
        inOrder(pNode.right);
    }
}


发表于 2020-04-23 14:27:38 回复(0)
/**
* 附上我的垃圾做法,一开始我也是用那种高大上的
* 判断是否有右节点,然后取父亲或祖父什么的。但是被要找最右节点的下一个就g了
* 所以重新用一种垃圾做法
*/
class Flag {
    boolean needMark = false;
}
public class Solution {
    public TreeLinkNode GetNext(TreeLinkNode pNode) {
        TreeLinkNode root = pNode;
        // 找到根节点
        while (root.next != null) {
            root = root.next;
        }
        List<TreeLinkNode> container = new ArrayList<>();
        /**
         * 中序遍历
         * pNode,当前节点,Flag用于标记是否需要获取pNode的下一个节点,container用于存储pNode的下一个节点
         */
        this.foreach(root, pNode, new Flag(), container);
        return container.isEmpty() ? null : container.get(0);
    }

    private void foreach(TreeLinkNode node, TreeLinkNode compare,
                         Flag needToMark, List<TreeLinkNode> container) {

        if (null == node || !container.isEmpty()) {
            return;
        }

        this.foreach(node.left, compare, needToMark, container);
        // 这里用于辨别是否需要添加pNode的下一个节点
        if (needToMark.needMark) {
            container.add(node);
        }
        
        // 判断是否比较的那个节点
        if (node == compare) {
            needToMark.needMark = true;
        }
        this.foreach(node.right, compare, needToMark, container);

    }
}  

/**
* 高大上的做法
*/
public class Solution {
    public TreeLinkNode GetNext(TreeLinkNode pNode) {
        // 空值处理
        if (null == pNode) {
            return pNode;
        }

        TreeLinkNode right = pNode.right;

        // 如果给定节点pNode无右儿子
        if (right == null) {
            TreeLinkNode parent = pNode.next;
            // 根节点
            if (parent == null) {
                return null;
            }
            // 如果给定节点是左儿子,那么返回父节点即可
            if (pNode == parent.left) {
                return parent;
            } else {
                // 这种情况就比较复杂点,但是其实本质就是找出pNode的父节点是否为祖父节点的左儿子就是,不是则继续找
                TreeLinkNode current = pNode;

                // 注意parent是对最右叶子节点没有不满足而导致找到根节点的情况
                while (parent != null && current == parent.right) {
                    current = parent;
                    parent = parent.next;
                }
                return current.next;
            }

        } else {
            // 有右儿子的情况最简单,只要找到右儿子的最左的叶子;无则返回右儿子
            TreeLinkNode current = right;
            while (current.left != null) {
                current = current.left;
            }
            return current;
        }
    }
}

编辑于 2020-03-26 22:42:18 回复(0)