二叉搜索树的最小绝对差

题目描述

力扣链接🔗

二叉搜索树的最小绝对差 - 图1

代码分析

数组法

还是可以利用二叉搜索树的特性,中序遍历之后的数组一定是递增的。但数组法的时间复杂度为O(n ^ n)。

  1. /**
  2. * 遍历搜索树为一个数组,进行判断即可(时间复杂度要高一点)
  3. *
  4. * @param root
  5. * @return
  6. */
  7. public int getMinimumDifference(TreeNode root) {
  8. traversal(root);
  9. for (int i = 1; i < res.size(); i++) {
  10. minValue = Math.min(minValue, Math.abs(res.get(i) - res.get(i - 1)));
  11. }
  12. return minValue;
  13. }
  14. List<Integer> res = new ArrayList<>();
  15. int minValue = Integer.MAX_VALUE;
  16. public TreeNode traversal(TreeNode root) {
  17. if (root == null) {
  18. return null;
  19. }
  20. traversal(root.left); // 左
  21. res.add(root.val);
  22. traversal(root.right); // 右
  23. return root;
  24. }

递归法

二叉搜索树的最小绝对差 - 图2

思路和验证二叉搜索树大体一致,需要找到最左边的节点来进行相减判断。

  1. /**
  2. * 递归法
  3. *
  4. * @param root
  5. * @return
  6. */
  7. public int getMinimumDifference(TreeNode root) {
  8. if (root == null) {
  9. return 0;
  10. }
  11. traversal(root);
  12. return minValue;
  13. }
  14. int minValue = Integer.MAX_VALUE;
  15. TreeNode pre; // 表示前一个节点,一定要定义为全局变量,在递归函数中定义,每次会重新赋值为null,就找不到上一个节点的值
  16. public TreeNode traversal(TreeNode root) {
  17. if (root == null) {
  18. return null;
  19. }
  20. traversal(root.left); // 左
  21. if (pre != null) minValue = Math.min(minValue, Math.abs(root.val - pre.val)); // 中
  22. pre = root;
  23. traversal(root.right); // 右
  24. return root;
  25. }

迭代法

和二叉搜索树的验证一致,也是获取上一个节点,但是判断条件有所改变。

  1. /**
  2. * 迭代法(中序)
  3. *
  4. * @param root
  5. * @return
  6. */
  7. public int getMinimumDifference(TreeNode root) {
  8. Stack<TreeNode> stack = new Stack<>();
  9. TreeNode cur = root;
  10. TreeNode pre = null;
  11. int minValue = Integer.MAX_VALUE;
  12. while (cur != null || !stack.isEmpty()) {
  13. if (cur != null) {
  14. stack.push(cur);
  15. cur = cur.left;
  16. } else {
  17. cur = stack.pop();
  18. if (pre != null) {
  19. minValue = Math.min(minValue, Math.abs(cur.val - pre.val));
  20. }
  21. pre = cur;
  22. cur = cur.right; // 获取右孩子
  23. }
  24. }
  25. return minValue;
  26. }