描述

示例

思路

利用了中序遍历的性质。中序遍历的步骤可表示为LTR，其中L代表左子树，T代表根结点，R代表右子树，即：先访问某结点的左子树，再访问该结点，再访问该结点的右子树。

「某结点的下一个结点」仅有二种情况：

• 若该结点存在右子树，则「下一个结点」为「该结点右子树的最左孩子」
• 若该结点不存在右子树，则「下一个结点」为「该结点的第一个右父结点」

代码

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

    }
};
*/
#include <ios>
class Solution {
  public:
    TreeLinkNode* GetNext(TreeLinkNode* pNode) {
        if (pNode == nullptr)
            return nullptr;
        //该节点若存在右子树
        if (pNode->right) {
            //若有右孩子，寻找右子树得到最左孩子
            TreeLinkNode* rightChild = pNode->right;
            while (rightChild->left)
                rightChild = rightChild->left;
            return rightChild;
        }
        //若不存在右子树，寻找第一个右祖先
        while (pNode->next) {
            if (pNode->next->left == pNode)
                return pNode->next;
            pNode = pNode->next;
        }
        return nullptr;

    }
};