题目描述
给定一个二叉搜索树的根结点 root, 返回树中任意两节点的差的最小值。
相关话题: 树、递归 难度: 简单
示例:
输入: root = [4,2,6,1,3,null,null]
输出: 1
解释:
注意,root是树结点对象(TreeNode object),而不是数组。
给定的树 [4,2,6,1,3,null,null] 可表示为下图:
4
/ \
2 6
/ \
1 3
最小的差值是 1, 它是节点1和节点2的差值, 也是节点3和节点2的差值。
注意:
- 二叉树的大小范围在 2 到 100。
- 二叉树总是有效的,每个节点的值都是整数,且不重复。
思路 1:
要求最小距离,又因为这是一棵二叉搜索树,它的中序遍历结果是升序的。所以可以将遍历结果保存下来,再计算两两相邻的结果的差值。
思路 2:
- 基于中序遍历,一边遍历一遍计算当前节点和它的前驱的差值。
- 细节,
pre[0] == Integer.MAX_VALUE
表示遍历到的是二叉搜索树的第一个节点,它没有前驱
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public int minDiffInBST(TreeNode root) {
int[] min = {Integer.MAX_VALUE};
int[] pre = {Integer.MAX_VALUE};
minDiffInBST(root, pre, min);
return min[0];
}
private void minDiffInBST(TreeNode root, int[] pre, int[] min){
if(root == null) return;
minDiffInBST(root.left, pre, min);
//pre[0] == Integer.MAX_VALUE表示遍历到的是二叉搜索树的第一个节点,它没有前驱
if(pre[0] == Integer.MAX_VALUE){
pre[0] = root.val;
}else{
min[0] = Math.min(min[0], root.val - pre[0]);
pre[0] = root.val;
}
minDiffInBST(root.right, pre, min);
}
}
不难发现,我们的private void minDiffInBST(TreeNode root, int[] pre, int[] min)
方法中记录前驱值的参数pre
和记录最小距离的参数min
都是数组类型。
我曾尝试过pre
使用int
型,认为每次调用minDiffInBST
传递给它就可以。然而,当我们分析中序遍历的过程,如下图
二叉树的遍历过程中, 每个节点都会被经过3次。而我们每次都是在第二次经过节点时,更新
pre
和min
。上图中可以看出,当遍历到节点
34
,pre
给更新为34,然后在递归节点34
的右子树时,从节点58
到节点44
,传递给minDiffInBST
方法的pre
参数都是34
,当递归返回时,很自然pre == 34
,这是不对的。因此,我们使用了数组来传递,当递归返回时,第二次经过节点44
,pre[0]被更新为44,这样返回到节点50
时才不会出错。(数组是关键,在返回过程中修改了pre[0]指向的那块内存的值,从而修改了递归调用时传递给方法的那块内存的值,地址不变,java只有值传递,而数组虽然也是传来了一个副本,但是它们都是指向同一块堆内存,修改内存中的值是可以的)
网友评论