leetcode刷题：二叉树22（二叉搜索树的最小绝对差）

530.二叉搜索树的最小绝对差

力扣题目链接

给你一棵所有节点为非负值的二叉搜索树，请你计算树中任意两节点的差的绝对值的最小值。

示例：

提示：树中至少有 2 个节点。

二叉搜索树，本身升序，非递减，中序遍历获取值，一个个比较

public int getMinimumDifference(TreeNode root) {
    
        List<Integer> result = new ArrayList();
        //遍历二叉树获取结果集
        //二叉搜索树本身就是升序的
        inorderTraversal(root, result);
        //定义一个不可能出现的最大值
        int minimumDifference = 100001;
        for (int i = 1; i < result.size(); i++) {
    
            if (minimumDifference == 0) {
    
                return minimumDifference;
            }
            if (result.get(i) - result.get(i - 1) < minimumDifference) {
    
                minimumDifference = result.get(i) - result.get(i - 1);
            }
        }
        return minimumDifference;
    }

    public void inorderTraversal(TreeNode root, List<Integer> result) {
    
        if (root == null) {
    
            return;
        }
        //中序遍历 左 中 右
        inorderTraversal(root.left, result);
        result.add(root.val);
        inorderTraversal(root.right, result);
    }

看看题解发现我写复杂了，题解的写法是用父指针，遍历中比较。

 TreeNode parent;
    int result = Integer.MAX_VALUE;

    public void inorderTraversalParent(TreeNode root) {
    
        if (root == null) {
    
            return;
        }
        //中序遍历 左 中 右
        inorderTraversalParent(root.left);
        if (parent != null) {
    
            if (result > root.val - parent.val) {
    
                result = root.val - parent.val
            }
        }
        parent = root;
        inorderTraversalParent(root.right);
    }

    public int getMinimumDifference2(TreeNode root) {
    
        inorderTraversalParent(root);
        return result;
    }