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

题目来源

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

题目描述

题目解析

中序遍历是一个升序数组，而最小值的产生一定是在数组中相邻两个元素的差之中，因此，在中序遍历时候抓住前一个数，和当前数字的差 于最小值作比较

递归

一定需要遍历所有节点，因为不知道到底是哪两个节点之间产生的。

用一个辅助链表，将中序遍历得到的值压入链表中，然后得到两个节点之间的值

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int getMinimumDifference(TreeNode root) {
        int ans = Integer.MAX_VALUE;
        ArrayList<Integer> list = new ArrayList<>();
        helper(root, list);
        int base = list.get(0);
        for (int i = 1; i < list.size(); i++){
            int t = list.get(i) - base;
            if (ans > t){
                ans = t;
            }
            base = list.get(i);
        }

        return ans;
    }

    private void helper(TreeNode root, ArrayList<Integer> list){
        if (root == null){
            return;
        }

        helper(root.left, list);
        list.add(root.val);
        helper(root.right, list);
    }
}

我们不需要所有链表的节点，只需要得到一个最小值就行了

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private int ans = Integer.MAX_VALUE;
    private TreeNode pre = null;
    public int getMinimumDifference(TreeNode root) {
        helper(root);
        return ans;
    }

    private void helper(TreeNode root){
        if (root == null){
            return;
        }

        helper(root.left);
        if (pre  != null){  // 不可能提前结束递归，必须遍历所有节点
            int t = root.val  - pre.val;
            if (ans > t){
                ans = t;
            }
        }
        pre = root;
        helper(root.right);
    }
}

辅助栈

中序递归的栈实现

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int getMinimumDifference(TreeNode root) {
        int ans = Integer.MAX_VALUE;
        TreeNode pre = null;
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.empty()){
            TreeNode top = stack.pop();
            if (top != null){
                if (top.right != null){
                    stack.push(top.right);
                }
                stack.push(top);
                stack.push(null);
                if (top.left != null){
                    stack.push(top.left);
                }
            }else{
                top = stack.pop();
                if (pre != null){
                    int t = top.val - pre.val;
                    if (ans > t){
                        ans = t;
                    }
                }
                pre = top;
            }
        }

        return ans;
    }

}

这道题考的是中序遍历，【层次遍历和中序遍历是不一样的】