算法数据结构

中序遍历过程中通过引用维护前驱

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

摘要: 中序遍历，通过引用维护前驱

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

中序遍历是二叉搜索树的重要操作，相关的问题很多，参考文章 二叉查找树的中序遍历和前驱后继。

有时在中序遍历过程中需要带着前驱节点，用于维护某些信息，此时可以通过传递引用参数来实现。本文解决两个相关的问题。

783. 二叉搜索树节点最小距离

给你一个二叉搜索树的根节点 root ，返回 树中任意两不同节点值之间的最小差值。

示例 1：
输入：root = [4,2,6,1,3]
输出：1
示例 2：
输入：root = [1,0,48,null,null,12,49]
输出：1

提示：

1
2
3
树中节点数目在范围 [2, 100] 内
0 <= Node.val <= 1e5
差值是一个正数，其数值等于两值之差的绝对值

代码 (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
28
class Solution {
public:
    int minDiffInBST(TreeNode* root) {
        int result = INT_MAX;
        TreeNode *precursor = nullptr;
        _inOrder(root, precursor, result);
        return result;
    }

private:
    void _inOrder(TreeNode* node, TreeNode*& precursor, int& result)
    {
        if(node -> left)
            _inOrder(node -> left, precursor, result);

        if(precursor)
        {
            int gap = node -> val - precursor -> val;
            if(gap < result)
                result = gap;
        }

        precursor = node;

        if(node -> right)
            _inOrder(node -> right, precursor, result);
    }
};

897. 递增顺序搜索树

给你一棵二叉搜索树，请你 按中序遍历 将其重新排列为一棵递增顺序搜索树，使树中最左边的节点成为树的根节点，并且每个节点没有左子节点，只有一个右子节点。

示例 1：
输入：root = [5,3,6,2,4,null,8,1,null,null,null,7,9]
输出：[1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9]
示例 2：
输入：root = [5,1,7]
输出：[1,null,5,null,7]

提示：

1
2
树中节点数的取值范围是 [1, 100]
0 <= Node.val <= 1000

代码 (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* increasingBST(TreeNode* root) {
        TreeNode *precursor = nullptr;
        TreeNode *result = nullptr;
        _inOrder(root, precursor, result);
        return result;
    }

private:
    void _inOrder(TreeNode* node, TreeNode*& precursor, TreeNode*& result)
    {
        if(node -> left)
            _inOrder(node -> left, precursor, result);

        if(!precursor)
            result = node;
        else
            precursor -> right = node;

        precursor = node;
        precursor -> left = nullptr;

        if(node -> right)
            _inOrder(node -> right, precursor, result);
    }
};
Share