二叉树的下一个节点

 来源：剑指offer面试题第8题

 【代码】

struct BinaryTreeNode {
    int val;
    BinaryTreeNode* parent;
    BinaryTreeNode* left;
    BinaryTreeNode* right;
};

BinaryTreeNode* GetNext(BinaryTreeNode* root) {
    if (root == NULL) return NULL;

    BinaryTreeNode* next_node = NULL;
    //如果节点有右子树，那么它的下一个节点就是它的右子树中最左边的节点
    if (root->right != NULL) {
        next_node = root->right;
        while (next_node->left != NULL) 
            next_node = next_node->left;
        return next_node;
    } 

    if (root->parent != NULL) {
        if (root == root->parent->left) {//当前节点是父节点的左子节点
            return root->parent;
        } else {
            BinaryTreeNode* parent_node = root->parent;
            BinaryTreeNode* current_node = root;
            while (parent_node != NULL && current_node == parent_node->left) {
                current_node = parent_node;
                parent_node = parent_node->parent;
            }

            return parent_node;
        }
    }

    return NULL;
}