题解 | 二叉树的下一个结点

2. 二叉树的下一个节点

二叉树的下一个结点_牛客题霸_牛客网

题目描述:给定一个二叉树其中的一个结点,请找出中序遍历顺序的下一个结点并且返回。

示例1:

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

  1. 如果一个节点有右子树,那么它的下一个节点就是它的右子树的最左节点
  2. 如果一个节点没有右子树 如果该节点是父节点的左孩子节点,那么下一个节点就是该节点的父节点如果该节点是父节点的右孩子节点,那么就一直向上找它的父节点,直到找到一个节点,是父节点的左孩子节点,此时下一个该节点的下一个节点就是该节点的父节点。如果找到根节点了,就证明到最后了,没有下一个节点了。
class Solution 
{
public:
    TreeLinkNode* GetNext(TreeLinkNode* pNode) 
    {
        // 1.一个节点有右子树
        if(pNode->right != nullptr) {
            pNode = pNode->right;
            while(pNode->left != nullptr)
                pNode = pNode->left;
            return pNode;
        }
        auto parent = pNode->next;
        // 2.1没有右子树, 该节点是父节点的左孩子节点
        if(parent != nullptr && parent->left == pNode)
            return parent;
        // 2.2没有右子树, 该节点是父节点的右孩子节点
        while(parent != nullptr) {
            pNode = parent;
            parent = pNode->next;
            if(parent == nullptr)    break;
            if(pNode == parent->left)
                return parent;
        }
        return nullptr;
    }
};

全部评论

相关推荐

06-07 12:20
新余学院 Java
点赞 评论 收藏
分享
酷酷我灵儿帅:这去不去和线不线下面说实话没啥关系
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-01 10:56
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务