主要内容 #

1. 问题描述
2. 求解思路
3. 参考代码

1. 问题描述 #

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

在图1中二叉树的中序遍历序列是{d, b, h, e, i, a, f, c, g}。我们将以这棵树为例来分析如何找出二叉树的下一个节点。

2. 求解思路

• 如果一个节点有右子树，那么它的下一个节点就是它右子树中的最左子节点。也就是说，从右节点出发，一直沿着指向左子节点的指针我们就就能找到它的下一个节点。例如，图1中节点b的下一个节点是h，节点a的下一个节点是f。
• 接着分析如果没有右子树的情形。如果节点是它父节点的左子节点，那么它的下一个节点就是它的父节点。例如图1中的节点d的下一个节点是b，节点f的下一个节点是c。
• 如果一个节点既没有右子树，并且它还是它父节点的有子节点，那么这种情况就比较复杂。我们可以沿着指向父节点的指针一直向上遍历，直到找到一个是它父节点的左子节点的节点。如果这样的节点存在，那么这个节点的父节点就是我们要找的下一个节点。
• 为了找到图1中i的下一个节点，我们沿着指向父节点的指针向上遍历，先到达节点e。由于节点e是它父节点b的右节点，我们继续向上遍历到达节点b。节点b是它父节点a的左子节点，因此节点b的父节点a就是节点i得下一个节点。
• 找到节点g的下一个节点的步骤类似。我们先沿着指向父节点的指针到达节点c。由于节点c是它父节点a的右子节点，我们继续向上遍历到节点a。由于节点a是树的根节点，他没有父节点，因此节点g没有下一个节点。

3. 参考代码 #

#include <iostream>
using namespace std;

struct BinaryTreeNode {
    int           value;
    BinaryTreeNode* left;
    BinaryTreeNode* right;
    BinaryTreeNode* parent;
    BinaryTreeNode(int data = int()) : value(data), left(nullptr), right(nullptr),
        parent(nullptr){
    }
};


class Solution {
public:
    BinaryTreeNode* GetNext (BinaryTreeNode* node){
        if (node == nullptr)
            return node;                  // return nullptr;

        if (node->right != nullptr) {     // 存在右子节点
            node = node->right;
            while (node->left != nullptr) // 直到是右子树中最左侧的节点
                node = node->left;
            return node;
        }
        else {                           // 不存在右子节点
            if (node->parent == nullptr) // 且不存在父节点
                return nullptr;
            else {
                // 沿着father域一直向上找，找到第一个是其father左儿子的节点，
                // 该节点的father就是当前节点的后继。
                BinaryTreeNode* father = node->parent;
                while (father != nullptr && father->right == node) {
                    node   = father;
                    father = father->parent;
                }
                return father;
            }
        }
    }
};