找出二叉树的下一个节点(代码实现和思路)

KLQ 2020-04-14 11:26:13 java常见问答 8096

下面给大家分享的是找二叉树的下一个节点的代码实现和思路,感兴趣的朋友可以进来了解一下,具体包含了3种思路代码实现方式。

题目:

指定一个二叉树和其中的一个结点,找出中序遍历顺序的下一个结点并返回。

注:树中的结点不仅仅包括了左右子结点,还包括了指向父结点的指针。

思路1:

首先我们要了解中序遍历的规则:左根右,之后作图。

找出二叉树的下一个节点

结合上面的图,大致可以分成2类:

1、有右子树的,则下一个结点就是右子树最左边的点;(eg:D,B,E,A,C,G)

2、没有右子树的,大致也可以分成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;
    }
};

这个思路是非常清晰清楚的哦!

思路2:

代码实现:

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
    }
}

思路3:

找出二叉树的下一个节点

1、假如,这个节点存在右子树,那么下一个节点为右子树最左子节点(如图节点B)

2、假如,这个节点不存在右子树。那么,这个时候就可以具体的分成两种情况:

(1)这个节点为父节点的左子节点,那么下一个节点为其父节点(如图节点D)

(2)这个节点为父节点的右子节点,那么沿着父节点向上遍历,直到找到一个节点的父节点的左子节点为该节点,那么该节点的父节点下一个节点(如图节点I,沿着父节点一直向上查找找到B(B为其父节点的左子节点),那么B的父节点A为下一个节点)。

代码实现:

public class Solution
{
    public TreeLinkNode GetNext(TreeLinkNode pNode)
    {
        if (pNode == null)
            return pNode;
        if (pNode.right != null)
        { // 节点有右子树
            pNode = pNode.right;
            while (pNode.left != null)
            {
                pNode = pNode.left;
            }
            return pNode;
        }
        else if (pNode.next != null && pNode.next.left == pNode)
        { // 节点无右子树且该节点为父节点的左子节点
            return pNode.next;
        }
        else if (pNode.next != null && pNode.next.right == pNode)
        { // 节点无右子树且该节点为父节点的右子节点
            while (pNode.next != null && pNode.next.left != pNode)
            {
                pNode = pNode.next;
            }
            return pNode.next;
        }
        else
        {
            return pNode.next; //节点无父节点 ,即节点为根节点
        }
    }
}

以上就是3种关于找出二叉树的下一个节点的代码实现和思路了,想了解更多的相关内容,可以继续的关注本站的Java实例专栏了解。