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

2019-06-05 本文已影响0人 topshi

题目描述

给定一个二叉搜索树的根结点 root, 返回树中任意两节点的差的最小值。
相关话题： 树、递归 难度： 简单

示例：
输入: root = [4,2,6,1,3,null,null]
输出: 1

解释:
注意，root是树结点对象(TreeNode object)，而不是数组。

给定的树 [4,2,6,1,3,null,null] 可表示为下图:

最小的差值是 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只有值传递，而数组虽然也是传来了一个副本，但是它们都是指向同一块堆内存，修改内存中的值是可以的)

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

题目描述

猜你喜欢

热点阅读