★【二叉搜索树】【中序遍历+前后指针】Leetcode 530. 二叉搜索树的最小绝对差
- 解法1 笨方法 中序遍历转化为有序数组之后遍历
- 解法2 记忆一下!!!需要用一个pre节点记录一下cur节点的前一个节点
遇到在二叉搜索树上求什么最值,求差值之类的,都要思考一下二叉搜索树可是有序的,要利用好这一特点。
同时要学会在递归遍历的过程中如何记录前后两个指针
---------------🎈🎈题目链接🎈🎈-------------------
解法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);// 右
}
}