算法数据结构

二叉查找树的中序遍历和前驱后继

字数统计: 609字   |   阅读时长: 2分
, ,

摘要: BST 的中序遍历，前驱和后继

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

中序遍历题目清单

有时在中序遍历过程中需要维护前驱 precursor，可以在递归函数中传递引用，参考文章 中序遍历过程中通过引用维护前驱。

中序遍历的前驱后继

模板题

给定一棵二叉搜索树和其中的一个节点 p ，找到该节点在树中的中序后继。如果节点没有中序后继，请返回 null 。

节点 p 的后继是值比 p.val 大的节点中键值最小的节点。

提示：

1
2
3
树中节点的数目在范围 [1, 1e4] 内。
-1e5 <= Node.val <= 1e5
树中各节点的值均保证唯一。

示例 1：
输入：root = [2,1,3], p = 1
输出：2
解释：这里 1 的中序后继是 2。请注意 p 和返回值都应是 TreeNode 类型。
示例 2：
输入：root = [5,3,6,2,4,null,null,1], p = 6
输出：null
解释：因为给出的节点没有中序后继，所以答案就返回 null 了。

代码 (C++，模板)

非递归找中序遍历的后继的代码模板。

此代码是找后继，找前驱的逻辑类似。

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
class Solution {
public:
    TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
        if(!root) return nullptr;
        TreeNode *iter = root;
        TreeNode *result = nullptr;
        while(true)
        {
            if(iter -> val <= p -> val)
            {
                if(iter -> right)
                    iter = iter -> right;
                else
                    break;
            }
            else
            {
                result = iter;
                if(iter -> left)
                    iter = iter -> left;
                else
                    break;
            }
        }
        return result;
    }
};

题目清单

Share