★【二叉搜索树】【中序遍历+前后指针】Leetcode 530. 二叉搜索树的最小绝对差

本文主要是介绍★【二叉搜索树】【中序遍历+前后指针】Leetcode 530. 二叉搜索树的最小绝对差，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

遇到在二叉搜索树上求什么最值，求差值之类的，都要思考一下二叉搜索树可是有序的，要利用好这一特点。
同时要学会在递归遍历的过程中如何记录前后两个指针

---------------🎈🎈题目链接🎈🎈-------------------

解法1 笨方法 中序遍历转化为有序数组之后遍历

最大值：Integer.MAX_VALUE
得到ArrayList中的值：arr.get(i)
得到ArrayList的大小：arr.size()

时间复杂度O(N)
空间复杂度O(N)

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public int getMinimumDifference(TreeNode root) {// 中序遍历转化为有序数组之后遍历List<Integer> arr = new ArrayList<>();helper(root,arr);int min = Integer.MAX_VALUE;for(int i = 0; i < arr.size()-1;i++){int temp = Math.abs(arr.get(i+1)-arr.get(i));if(temp < min){min = temp;}}return min;}public void helper(TreeNode root, List<Integer> arr){if(root==null) return;helper(root.left, arr);arr.add(root.val);helper(root.right, arr);}
}

解法2 记忆一下！！！需要用一个pre节点记录一下cur节点的前一个节点

以上代码是把二叉搜索树转化为有序数组了，其实在二叉搜素树中序遍历的过程中，我们就可以直接计算了。
需要用一个pre节点记录一下cur节点的前一个节点

时间复杂度O(N)
空间复杂度O(N)

可以背一下背一下

// 采用一个pre节点记录一下cur节点的前一个节点 + 中序遍历【模板题】
class Solution {int result = Integer.MAX_VALUE;TreeNode pre = null;public int getMinimumDifference(TreeNode root) {helper(root);return result;}public void helper(TreeNode root){if(root==null) return;helper(root.left);// 左if(pre!=null){result = Math.min(result,Math.abs(root.val-pre.val));}pre = root;helper(root.right);// 右}
}

这篇关于★【二叉搜索树】【中序遍历+前后指针】Leetcode 530. 二叉搜索树的最小绝对差的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---