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

  |  

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

【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】
我的网站:潮汐朝夕的生活实验室
我的公众号:算法题刷刷
我的知乎:潮汐朝夕
我的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 <= 105
差值是一个正数,其数值等于两值之差的绝对值

代码 (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