算法刷题目二叉树
Source
Edit
History

二叉树中找节点的后继节点

二叉树中找节点的后继节点

一、题目

给一个二叉树，这个二叉树的节点结构中多了一个父亲节点。如下

1
2
3
4
5
6
7
8
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode* parent;

    explicit TreeNode(int val) : val(val), left(nullptr), right(nullptr) {}
};

寻找这种二叉树中某个节点的后继节点。

二、思路

常规的解法中，我们的对二叉树的中序遍历就可以解决这个问题。但是二叉树的中序遍历的方法求解此题是一个时间复杂度为 O(N)，空间复杂度为 O(N) 的方法，因为要使用到栈保存元素。

因此我们寻找其他方法，要利用好当前树的结构中的父节点。

  1. 第一种情况，如果这个节点有右子树，那么这个节点的后继节点就是他的右子树上最左的节点
  2. 第二种情况，如果这个节点没有右子树。当前节点即为 n，他的父节点记为 f
    1. 如果 n 是 f 的左子节点，那么 f 就是n 的后继节点
    2. 如果 n 是 f 的右子节点，那么需要往上找，一直找到一个节点 s，节点 s 的他的父节点的左子节点，那么节点的 s 的父节点就是 n 的后继节点。
    3. 如果上一步一直找到父节点为空都没有找到，那么说明 n 没有后继节点

三、code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
TreeNode* get_next_node(TreeNode* node) {
    if (node == nullptr) return nullptr;
    if (node->right != nullptr) {
        node = node->right;
        for (; node->left != nullptr;) {
            node = node->left;
        }
        return node;
    }
    TreeNode* parent = node->parent;
    for (; parent != nullptr;) {
        if (parent->left == node) {
            return parent;
        }
        node = parent;
        parent = parent->parent;
    }
    return nullptr;
}

假设 n 和他的后继节点之间是 L 个位置，那么时间复杂度就是 O(L)。没有用到其他辅助内存，空间复杂度为 O(1)