530. Minimum Absolute Difference in BST.md

530. Minimum Absolute Difference in BST

---

leetcode-cn Daily Challenge on October 12th, 2020.

---

Difficulty : Easy

Related Topics : Tree

---

Given a binary search tree with non-negative values, find the minimum absolute difference between values of any two nodes.

Example:

Input:

   1
    \
     3
    /
   2

Output:
1

Explanation:
The minimum absolute difference is 1, which is the difference between 2 and 1 (or between 2 and 3).

Note:

• There are at least two nodes in this BST.
• This question is the same as 783: https://leetcode.com/problems/minimum-distance-between-bst-nodes/

---

Solution

• mine
  • Java

    • Sort Runtime: 4 ms, faster than 12.91%, Memory Usage: 40 MB, less than 73.08% of Java online submissions

      // O(N*LogN)time O(N)space
      // N is the node count
      public int getMinimumDifference(TreeNode root) {
          List<Integer> list = new ArrayList<>();
          dfs(root,list);
          if(list.size() == 0){
              return 0;
          }
          int res = Integer.MAX_VALUE;;
          Collections.sort(list);
          for(int i = 1; i < list.size(); i++){
              res = Math.min(res, list.get(i) - list.get(i - 1));
          }
          return res;
      
      }
      public void dfs(TreeNode node, List<Integer> list){
          if(node != null){
              list.add(node.val);
              dfs(node.left, list);
              dfs(node.right, list);
          }
      }
      

    • Iterate & LinkedList Runtime: 2 ms, faster than 23.90%, Memory Usage: 39.6 MB, less than 88.46% of Java online submissions

      // O(N)time O(N)space
      // N is the node count
      public int getMinimumDifference(TreeNode root) {
          LinkedList<Integer> list = new LinkedList<>();
          LinkedList<TreeNode> nodes = new LinkedList<>();
          TreeNode cur =  root;
          while(cur != null || !nodes.isEmpty()){
              if(cur != null){
                  if(cur.left != null){
                      nodes.push(cur);
                      cur = cur.left;
                  }else{
                      list.add(cur.val);
                      cur = cur.right;
                  }
              }else{
                  cur = nodes.pop();
                  list.add(cur.val);
                  cur = cur.right;
              }
          }
          int res = Integer.MAX_VALUE;
          int pre = list.removeFirst();
          while(!list.isEmpty()){
              res = Math.min(res,list.getFirst() - pre);
              pre = list.removeFirst();
          }
          return res;
      }
      

    • Recursive Runtime: 0 ms, faster than 100.00%, Memory Usage: 39.1 MB, less than 92.31% of Java online submissions

      // O(N)time O(D)space
      // N is the node count
      // D is the root deep
      Integer res = Integer.MAX_VALUE, pre = null;
      public int getMinimumDifference(TreeNode root) {
          if (root.left != null) getMinimumDifference(root.left);
          if (pre != null) res = Math.min(res, root.val - pre);
          pre = root.val;
          if (root.right != null) getMinimumDifference(root.right);
          return res;
      }
      

---