美文网首页
leetcode 783. 二叉搜索树结点最小距离

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

作者: topshi | 来源:发表于2019-06-05 15:40 被阅读0次

    题目描述

    给定一个二叉搜索树的根结点 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次。而我们每次都是在第二次经过节点时,更新premin
    上图中可以看出,当遍历到节点34pre给更新为34,然后在递归节点34的右子树时,从节点58到节点44,传递给minDiffInBST方法的pre参数都是34,当递归返回时,很自然pre == 34,这是不对的。因此,我们使用了数组来传递,当递归返回时,第二次经过节点44,pre[0]被更新为44,这样返回到节点50时才不会出错。(数组是关键,在返回过程中修改了pre[0]指向的那块内存的值,从而修改了递归调用时传递给方法的那块内存的值,地址不变,java只有值传递,而数组虽然也是传来了一个副本,但是它们都是指向同一块堆内存,修改内存中的值是可以的)

    相关文章

      网友评论

          本文标题:leetcode 783. 二叉搜索树结点最小距离

          本文链接:https://www.haomeiwen.com/subject/dptsxctx.html