The sword points to Offer57 — the next node in the binary tree

Topic describes

Given a binary tree and one of its nodes, find the next node in the middle traversal order and return. Note that the nodes in the tree contain not only the left and right children, but also Pointers to the parent.

Answer key

#include <iostream>

using namespace std;

struct TreeLinkNode {
    int val;
    struct TreeLinkNode *left;
    struct TreeLinkNode *right;
    struct TreeLinkNode *next;

    TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}

    TreeLinkNode() {}};TreeLinkNode *newTree(a) {
    TreeLinkNode *node = new TreeLinkNode;
    int x;
    cin >> x;
    if(! x)node =NULL;
    else {
        node->val = x;
        node->left->next = node;
        node->left = newTree(a); node->right->next = node; node->right =newTree(a); }return node;
}

TreeLinkNode *GetNext(TreeLinkNode *pNode) {
    if(! pNode)return NULL;
    if (pNode->right) {
        pNode = pNode->right;
        while (pNode->left)pNode = pNode->left;
        return pNode;
    }
    while (pNode->next) {
        if (pNode->next->left == pNode)
            return pNode->next;
        pNode = pNode->next;
    }
    return NULL;
}

int main(a) {
    ios::sync_with_stdio(false);
    TreeLinkNode *node = newTree(a); TreeLinkNode *pNode; TreeLinkNode *res =GetNext(pNode);
    cout << res->val;
    return 0;
}
Copy the code