剑指57-二叉树的下一个结点

中序遍历

题目描述

给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。

其实刚开始做题我还是有点迷惑的，按理说这个算法的参数不应该是给出一个二叉树和一个结点吗，而这里只给了一个参数，后来想了一下，这个参数不仅是一个二叉树，同时也是要指定的要找下一个结点的结点

解法

1. 如果有右结点，下一个就是右子树的最左结点
2. 如果没有右结点，而且是父节点的左结点
3. 如果没有右结点，而且是父节点的右结点，则应该找到其祖先结点里，第一个该祖先结点为其父节点的左结点的这样一个结点，听起来有点拗口

我们分别来看看这三种情况

情况1：如果有右结点，下一个就是右子树的最左结点，这个应该比较好理解

情况2：如果没有右结点，而且是父节点的左结点

情况3：如果没有右结点，而且是父节点的右结点

代码

struct TreeLinkNode {
    int val;
    struct TreeLinkNode *left;
    struct TreeLinkNode *right;
    struct TreeLinkNode *next;
    TreeLinkNode(int x) :val(x), left(nullptr), right(nullptr), next(nullptr) {

    }
};

class Solution {
public:
    TreeLinkNode* GetNext(TreeLinkNode* pNode)
    {
        if (!pNode) return pNode;
        if (pNode->right) return inorderTraverse(pNode->right); //如果有右结点，下一个就是右子树的最左结点
        else if (pNode->next && pNode->next->left == pNode) { //如果没有右结点，而且是父节点的左结点
            return pNode->next;
        }
        else if (pNode->next && pNode->next->right == pNode) //如果没有右结点，而且是父节点的右结点
        {
            //这里是个难点，应该找到其祖先结点里，第一个该祖先结点为其父节点的左结点的这样一个结点，听起来有点拗口
            while (pNode->next) {
                TreeLinkNode *root = pNode->next;
                if (root->left == pNode) {
                    return root;
                }
                pNode = pNode->next;
            }
        }
        return nullptr;
    }

    TreeLinkNode* inorderTraverse(TreeLinkNode* root) //找到最左的结点
    {
        if (!root) return root;
        if (root->left) return inorderTraverse(root->left);
        else return root;
    }
};