参与本项目，贡献其他语言版本的代码，拥抱开源，让更多学习算法的小伙伴们收益！

利用二叉搜索树的特性搞起！

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

力扣题目链接

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

示例：

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

视频讲解

《代码随想录》算法视频公开课：二叉搜索树中，需要掌握如何双指针遍历！| LeetCode：530.二叉搜索树的最小绝对差，相信结合视频在看本篇题解，更有助于大家对本题的理解。

思路

题目中要求在二叉搜索树上任意两节点的差的绝对值的最小值。

注意是二叉搜索树，二叉搜索树可是有序的。

遇到在二叉搜索树上求什么最值啊，差值之类的，就把它想成在一个有序数组上求最值，求差值，这样就简单多了。

递归

那么二叉搜索树采用中序遍历，其实就是一个有序数组。

在一个有序数组上求两个数最小差值，这是不是就是一道送分题了。

最直观的想法，就是把二叉搜索树转换成有序数组，然后遍历一遍数组，就统计出来最小差值了。

代码如下：

class Solution {
private:
vector<int> vec;
void traversal(TreeNode* root) {
    if (root == NULL) return;
    traversal(root->left);
    vec.push_back(root->val); // 将二叉搜索树转换为有序数组
    traversal(root->right);
}
public:
    int getMinimumDifference(TreeNode* root) {
        vec.clear();
        traversal(root);
        if (vec.size() < 2) return 0;
        int result = INT_MAX;
        for (int i = 1; i < vec.size(); i++) { // 统计有序数组的最小差值
            result = min(result, vec[i] - vec[i-1]);
        }
        return result;
    }
};

以上代码是把二叉搜索树转化为有序数组了，其实在二叉搜素树中序遍历的过程中，我们就可以直接计算了。

需要用一个pre节点记录一下cur节点的前一个节点。

如图：

一些同学不知道在递归中如何记录前一个节点的指针，其实实现起来是很简单的，大家只要看过一次，写过一次，就掌握了。

代码如下：

class Solution {
private:
int result = INT_MAX;
TreeNode* pre = NULL;
void traversal(TreeNode* cur) {
    if (cur == NULL) return;
    traversal(cur->left);   // 左
    if (pre != NULL){       // 中
        result = min(result, cur->val - pre->val);
    }
    pre = cur; // 记录前一个
    traversal(cur->right);  // 右
}
public:
    int getMinimumDifference(TreeNode* root) {
        traversal(root);
        return result;
    }
};

是不是看上去也并不复杂！

迭代

看过这两篇二叉树：听说递归能做的，栈也能做！，二叉树：前中后序迭代方式的写法就不能统一一下么？文章之后，不难写出两种中序遍历的迭代法。

下面我给出其中的一种中序遍历的迭代法，代码如下：

class Solution {
public:
    int getMinimumDifference(TreeNode* root) {
        stack<TreeNode*> st;
        TreeNode* cur = root;
        TreeNode* pre = NULL;
        int result = INT_MAX;
        while (cur != NULL || !st.empty()) {
            if (cur != NULL) { // 指针来访问节点，访问到最底层
                st.push(cur); // 将访问的节点放进栈
                cur = cur->left;                // 左
            } else {
                cur = st.top();
                st.pop();
                if (pre != NULL) {              // 中
                    result = min(result, cur->val - pre->val);
                }
                pre = cur;
                cur = cur->right;               // 右
            }
        }
        return result;
    }
};

总结

遇到在二叉搜索树上求什么最值，求差值之类的，都要思考一下二叉搜索树可是有序的，要利用好这一特点。

同时要学会在递归遍历的过程中如何记录前后两个指针，这也是一个小技巧，学会了还是很受用的。

后面我将继续介绍一系列利用二叉搜索树特性的题目。

其他语言版本

Java

递归

class Solution {
    TreeNode pre;// 记录上一个遍历的结点
    int result = Integer.MAX_VALUE;
    public int getMinimumDifference(TreeNode root) {
       if(root==null)return 0;
       traversal(root);
       return result;
    }
    public void traversal(TreeNode root){
        if(root==null)return;
        //左
        traversal(root.left);
        //中
        if(pre!=null){
            result = Math.min(result,root.val-pre.val);
        }
        pre = root;
        //右
        traversal(root.right);
    }
}

統一迭代法-中序遍历

class Solution {
    public int getMinimumDifference(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode pre = null;
        int result = Integer.MAX_VALUE;

        if(root != null)
            stack.add(root);
        while(!stack.isEmpty()){
            TreeNode curr = stack.peek();
            if(curr != null){
                stack.pop();
                if(curr.right != null)
                    stack.add(curr.right);
                stack.add(curr);
                stack.add(null);
                if(curr.left != null)
                    stack.add(curr.left);
            }else{
                stack.pop();
                TreeNode temp = stack.pop();
                if(pre != null)
                    result = Math.min(result, temp.val - pre.val);
                pre = temp;
            }
        }
        return result;
    }
}

迭代法-中序遍历

class Solution {
    TreeNode pre;
    Stack<TreeNode> stack;
    public int getMinimumDifference(TreeNode root) {
        if (root == null) return 0;
        stack = new Stack<>();
        TreeNode cur = root;
        int result = Integer.MAX_VALUE;
        while (cur != null || !stack.isEmpty()) {
            if (cur != null) {
                stack.push(cur); // 将访问的节点放进栈
                cur = cur.left; // 左
            }else {
                cur = stack.pop(); 
                if (pre != null) { // 中
                    result = Math.min(result, cur.val - pre.val);
                }
                pre = cur;
                cur = cur.right; // 右
            }
        }
        return result;
    }
}

Python

递归

class Solution:
    def getMinimumDifference(self, root: TreeNode) -> int:
        res = []   
        r = float("inf")
        def buildaList(root):  //把二叉搜索树转换成有序数组
            if not root: return None
            if root.left: buildaList(root.left)  //左
            res.append(root.val)  //中
            if root.right: buildaList(root.right)  //右
            return res
            
        buildaList(root)
        for i in range(len(res)-1):  // 统计有序数组的最小差值
            r = min(abs(res[i]-res[i+1]),r)
        return r
        
        
class Solution: # 双指针法，不用数组 (同Carl写法) - 更快
    def getMinimumDifference(self, root: Optional[TreeNode]) -> int:
        global pre,minval
        pre = None
        minval = 10**5
        self.traversal(root)
        return minval

    def traversal(self,root):
        global pre,minval
        if not root: return None
        self.traversal(root.left)
        if pre and root.val-pre.val<minval: 
            minval = root.val-pre.val
        pre = root
        self.traversal(root.right)

迭代法-中序遍历

class Solution:
    def getMinimumDifference(self, root: TreeNode) -> int:
        stack = []
        cur = root
        pre = None
        result = float('inf')
        while cur or stack:
            if cur: # 指针来访问节点，访问到最底层
                stack.append(cur)
                cur = cur.left
            else: # 逐一处理节点
                cur = stack.pop()
                if pre: # 当前节点和前节点的值的差值
                    result = min(result, abs(cur.val - pre.val))
                pre = cur
                cur = cur.right
        return result

Go：

中序遍历，然后计算最小差值

// 中序遍历的同时计算最小值
func getMinimumDifference(root *TreeNode) int {
    // 保留前一个节点的指针
    var prev *TreeNode
    // 定义一个比较大的值
    min := math.MaxInt64
    var travel func(node *TreeNode)
    travel = func(node *TreeNode) {
        if node == nil {
            return 
        }
        travel(node.Left)
        if prev != nil && node.Val - prev.Val < min {
            min = node.Val - prev.Val
        }
        prev = node
        travel(node.Right)
    }
    travel(root)
    return min
}

JavaScript

递归先转换为有序数组

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var getMinimumDifference = function (root) {
    let arr = [];
    const buildArr = (root) => {
        if (root) {
            buildArr(root.left);
            arr.push(root.val);
            buildArr(root.right);
        }
    }
    buildArr(root);
    let diff = arr[arr.length - 1];
    for (let i = 1; i < arr.length; ++i) {
        if (diff > arr[i] - arr[i - 1])
            diff = arr[i] - arr[i - 1];
    }
    return diff;
};

递归在递归的过程中更新最小值

var getMinimumDifference = function(root) {
    let res = Infinity
    let preNode = null
    // 中序遍历
    const inorder = (node) => {
        if(!node) return
        inorder(node.left)
        // 更新res
        if(preNode) res = Math.min(res, node.val - preNode.val)
        // 记录前一个节点         
        preNode = node
        inorder(node.right)
    }
    inorder(root)
    return res
}

迭代中序遍历

var getMinimumDifference = function(root) {
    let stack = []
    let cur = root
    let res = Infinity
    let pre = null
    while(cur || stack.length) {
        if(cur) {
            stack.push(cur)
            cur = cur.left
        } else {
            cur = stack.pop()
            if(pre) res = Math.min(res, cur.val - pre.val)
            pre = cur
            cur = cur.right
        }
    }
    return res
}

TypeScript

辅助数组解决

function getMinimumDifference(root: TreeNode | null): number {
    let helperArr: number[] = [];
    function recur(root: TreeNode | null): void {
        if (root === null) return;
        recur(root.left);
        helperArr.push(root.val);
        recur(root.right);
    }
    recur(root);
    let resMin: number = Infinity;
    for (let i = 0, length = helperArr.length; i < length - 1; i++) {
        resMin = Math.min(resMin, helperArr[i + 1] - helperArr[i]);
    }
    return resMin;
};

递归中解决

function getMinimumDifference(root: TreeNode | null): number {
    let preNode: TreeNode | null= null;
    let resMin: number = Infinity;
    function recur(root: TreeNode | null): void {
        if (root === null) return;
        recur(root.left);
        if (preNode !== null) {
            resMin = Math.min(resMin, root.val - preNode.val);
        }
        preNode = root;
        recur(root.right);
    }
    recur(root);
    return resMin;
};

迭代法-中序遍历

function getMinimumDifference(root: TreeNode | null): number {
    const helperStack: TreeNode[] = [];
    let curNode: TreeNode | null = root;
    let resMin: number = Infinity;
    let preNode: TreeNode | null = null;
    while (curNode !== null || helperStack.length > 0) {
        if (curNode !== null) {
            helperStack.push(curNode);
            curNode = curNode.left;
        } else {
            curNode = helperStack.pop()!;
            if (preNode !== null) {
                resMin = Math.min(resMin, curNode.val - preNode.val);
            }
            preNode = curNode;
            curNode = curNode.right;
        }
    }
    return resMin;
};

Scala

构建二叉树的有序数组:

object Solution {
  import scala.collection.mutable
  def getMinimumDifference(root: TreeNode): Int = {
    val arr = mutable.ArrayBuffer[Int]()
    def traversal(node: TreeNode): Unit = {
      if (node == null) return
      traversal(node.left)
      arr.append(node.value)
      traversal(node.right)
    }
    traversal(root)
    // 在有序数组上求最小差值
    var result = Int.MaxValue
    for (i <- 1 until arr.size) {
      result = math.min(result, arr(i) - arr(i - 1))
    }
    result // 返回最小差值
  }
}

递归记录前一个节点:

object Solution {
  def getMinimumDifference(root: TreeNode): Int = {
    var result = Int.MaxValue // 初始化为最大值
    var pre: TreeNode = null // 记录前一个节点

    def traversal(cur: TreeNode): Unit = {
      if (cur == null) return
      traversal(cur.left)
      if (pre != null) {
        // 对比result与节点之间的差值
        result = math.min(result, cur.value - pre.value)
      }
      pre = cur
      traversal(cur.right)
    }

    traversal(root)
    result // return关键字可以省略
  }
}

迭代解决:

object Solution {
  import scala.collection.mutable
  def getMinimumDifference(root: TreeNode): Int = {
    var result = Int.MaxValue // 初始化为最大值
    var pre: TreeNode = null // 记录前一个节点
    var cur = root
    var stack = mutable.Stack[TreeNode]()
    while (cur != null || !stack.isEmpty) {
      if (cur != null) {
        stack.push(cur)
        cur = cur.left
      } else {
        cur = stack.pop()
        if (pre != null) {
          result = math.min(result, cur.value - pre.value)
        }
        pre = cur
        cur = cur.right
      }
    }
    result // return关键字可以省略
  }
}

rust

构建二叉树的有序数组:

use std::cell::RefCell;
use std::rc::Rc;
impl Solution {
    pub fn get_minimum_difference(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
        let mut vec = vec![];
        Self::traversal(root, &mut vec);
        let mut min = i32::MAX;
        for i in 1..vec.len() {
            min = min.min(vec[i] - vec[i - 1])
        }
        min
    }
    pub fn traversal(root: Option<Rc<RefCell<TreeNode>>>, v: &mut Vec<i32>) {
        if root.is_none() {
            return;
        }
        let node = root.as_ref().unwrap().borrow();
        Self::traversal(node.left.clone(), v);
        v.push(node.val);
        Self::traversal(node.right.clone(), v);
    }
}

递归中解决

impl Solution {
    pub fn get_minimum_difference(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
        let mut pre = None;
        let mut min = i32::MAX;
        Self::inorder(root, &mut pre, &mut min);
        min
    }
    pub fn inorder(root: Option<Rc<RefCell<TreeNode>>>, pre: &mut Option<i32>, min: &mut i32) {
        if root.is_none() {
            return;
        }
        let node = root.as_ref().unwrap().borrow();
        Self::inorder(node.left.clone(), pre, min);
        if let Some(pre) = pre {
            *min = (node.val - *pre).min(*min);
        }
        *pre = Some(node.val);

        Self::inorder(node.right.clone(), pre, min);
    }
}

迭代

impl Solution {
    pub fn get_minimum_difference(mut root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
        if root.is_none() {
            return 0;
        }
        let mut stack = vec![];
        let mut pre = -1;
        let mut res = i32::MAX;
        while root.is_some() || !stack.is_empty() {
            while let Some(node) = root {
                root = node.borrow().left.clone();
                stack.push(node);
            }

            let node = stack.pop().unwrap();

            if pre >= 0 {
                res = res.min(node.borrow().val - pre);
            }

            pre = node.borrow().val;

            root = node.borrow().right.clone();
        }
        res
    }
}

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

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

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

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

视频讲解

思路

递归

迭代

总结

其他语言版本

Java

Python

Go：

JavaScript

TypeScript

Scala

rust

Files

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

Latest commit

History

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

File metadata and controls

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

视频讲解

思路

递归

迭代

总结

其他语言版本

Java

Python

Go：

JavaScript

TypeScript

Scala

rust