08.二叉树的下一个结点*

题目描述*

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

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) {
        if(pNode == nullptr) {
            return nullptr;
        }
        if(pNode->right == nullptr) {
            while(pNode->next != nullptr) {
                TreeLinkNode *root = pNode->next;
                if(root->left == pNode) {
                    return root;
                }
                pNode = pNode->next;
            }
        }else {
            TreeLinkNode *p = pNode->right;
            while(p->left != nullptr) {
                p = p->left;
            }
            return p;
        }
        return nullptr;
    }
};

最后更新: July 23, 2022