二叉搜索树中序后继

发表于

给定一个结点，找出这个结点的后继结点
中序遍历：左 中 右
情况分类：
一：结点的右子树不为空
返回右子树的最左结点
二：结点的右子树为空
1.如果这个结点是根结点，直接返回NULL
2.如果这个结点是父节点的左儿子，直接返回父亲结点
3.如果这个结点是父节点的右儿子，不断向上找第一个结点，这个结点是他父亲结点的左儿子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
// Definition for a Node.
/*
class Node {
public:
    int val;
    Node* left;
    Node* right;
    Node* parent;
};
*/
class Solution {
public:
    Node* inorderSuccessor(Node* node) {
        
        if (node->right) {
            Node* p = node->right;
            while (p->left) {
                p = p->left;
            }
            return p;
        } else {
            if (node->parent == NULL) 
                return NULL;
            if (node->parent->left == node) 
                return node->parent;
            else {
                    Node *p = node->parent;
                    while (p && p->right == node) {
                        node = p;
                        p = p->parent;
                    }
                    return p;
            }
        }
    }
};