about BinarySearchTree 2

Sat, Sep 4, 2021 10-minute read

master BST in algo

Maximum Binary Tree 654

You are given an integer array nums with no duplicates. A maximum binary tree can be built recursively from nums using the following algorithm:

Create a root node whose value is the maximum value in nums.
Recursively build the left subtree on the subarray prefix to the left of the maximum value.
Recursively build the right subtree on the subarray suffix to the right of the maximum value.
Return the maximum binary tree built from nums.

这题非常简单，就是找最大值，但是呢，思路都好了后，递归完结条件忘了。。

如果为空，返 null； 如果只有一个元素，返回这个元素

Minimum Absolute Difference in BST 530

Given the root of a Binary Search Tree (BST), return the minimum absolute difference between the values of any two different nodes in the tree.

Input: root = [4,2,6,1,3]
Output: 1

这题我写的非常差，还是不熟悉中序遍历的 BST， 其实就是一个数值增大的数组。

其实就是从最左边开始处理，一个个往上往右边， 那么最小绝对差肯定在相邻的两个节点值之间产生。所以我们的做法就是对 BST 进行中序遍历，然后当前节点值和之前节点值求绝对差并更新结果 res

 TreeNode prev;
    
   int result = Integer.MAX_VALUE; 
    public int getMinimumDifference(TreeNode root) {
        
        helper(root);
        return result;
    }
    
    private void helper(TreeNode root) {
        if (root == null) {
            return;
        }
        
        helper(root.left);
        
        if (prev != null) {
            result = Math.min(result, root.val - prev.val);
        }
        prev = root;
        
        helper(root.right);
    }

global variables are generally discouraged. It’s probably worth passing mutable values

public int getMinimumDifference(TreeNode root) {
    	List<Integer> prev = new ArrayList<>(); // contains at most 1 value
    	int[] min = new int[]{Integer.MAX_VALUE};
    	inorder(root, prev, min);
    	return min[0];
    }
    
    private void inorder(TreeNode root, List<Integer> prev, int[] min) {
    	if (root == null) return;
    	
    	inorder(root.left, prev, min);
    	if (prev.isEmpty()) {
    		prev.add(root.val);
    	} else {
    		min[0] = Math.min(min[0], Math.abs(root.val - prev.get(0)));
    		prev.set(0, root.val);
    	}
    	inorder(root.right, prev, min);    	
    }

Closest Binary Search Tree Value 270

Given a non-empty binary search tree and a target value, find the value in the BST that is closest to the target.

Note:

Given target value is a floating point.
You are guaranteed to have only one unique value in the BST that is closest to the target.
Example:

Input: root = [4,2,5,1,3], target = 3.714286

    4
   / \
  2   5
 / \
1   3

Output: 4

中序遍历来做，一个一个的比较，维护一个最小值，不停的更新，实际上这种方法并没有提高效率，用其他的遍历方法也可以

二分搜索树的特点 (左<根<右) 来快速定位，由于根节点是中间值，在往下遍历时，根据目标值和根节点的值大小关系来比较，如果目标值小于节点值，则应该找更小的值，于是到左子树去找

 public int closest(TreeNode root, int target) {
    int res = root.key;

    while (root != null) {
      if (Math.abs(res - target) >= Math.abs(root.key - target)) {
        res = root.key;
      }
      root = target < root.key ? root.left : root.right;
    }
    return res;
  }

Find Mode in Binary Search Tree 501

Given the root of a binary search tree (BST) with duplicates, return all the mode(s) (i.e., the most frequently occurred element) in it.

If the tree has more than one mode, return them in any order.

Assume a BST is defined as follows:

The left subtree of a node contains only nodes with keys less than or equal to the node's key.
The right subtree of a node contains only nodes with keys greater than or equal to the node's key.
Both the left and right subtrees must also be binary search trees.
 

Example 1:


Input: root = [1,null,2,2]
Output: [2]

TreeNode prev;
    ArrayList<Integer> res;
    int count;
    int maxCount;
    
    public int[] findMode(TreeNode root) {
       res = new ArrayList<>();
        maxCount = 0;
        count = 0;
        helper(root);
        int[] ans = new int[res.size()];
        for (int i = 0; i < res.size(); i++) {
            ans[i] = res.get(i);
        }
        return ans;
    }
    
    private void helper(TreeNode root) {
        if (root == null) {
            return;
        }
        
       
        
        helper(root.left);
        
         count = prev != null && prev.val == root.val ? count + 1 : 1;
        
        if (count == maxCount) {
            res.add(root.val);
        } else if (count > maxCount) {
            res.clear();
            res.add(root.val);
            maxCount = count;
        }
        prev = root;
        
        
        helper(root.right);
    }

Lowest Common Ancestor of a Binary Tree 236

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

 

Example 1:


Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output: 3
Explanation: The LCA of nodes 5 and 1 is 3.

在二叉树中来搜索 p 和 q，然后从路径中找到最后一个相同的节点即为父节点，可以用递归来实现，在递归函数中，首先看当前结点是否为空，若为空则直接返回空，若为 p 或 q 中的任意一个，也直接返回当前结点。否则的话就对其左右子结点分别调用递归函数，由于这道题限制了 p 和 q 一定都在二叉树中存在，那么如果当前结点不等于 p 或 q，p 和 q 要么分别位于左右子树中，要么同时位于左子树，或者同时位于右子树，那么我们分别来讨论：

  • 若 p 和 q 分别位于左右子树中，那么对左右子结点调用递归函数，会分别返回 p 和 q 结点的位置，而当前结点正好就是 p 和 q 的最小共同父结点，直接返回当前结点即可，这就是题目中的例子 1 的情况。

  • 若 p 和 q 同时位于左子树，这里有两种情况，一种情况是 left 会返回 p 和 q 中较高的那个位置，而 right 会返回空，所以最终返回非空的 left 即可，这就是题目中的例子 2 的情况。还有一种情况是会返回 p 和 q 的最小父结点，就是说当前结点的左子树中的某个结点才是 p 和 q 的最小父结点，会被返回。

  • 若 p 和 q 同时位于右子树，同样这里有两种情况，一种情况是 right 会返回 p 和 q 中较高的那个位置，而 left 会返回空，所以最终返回非空的 right 即可，还有一种情况是会返回 p 和 q 的最小父结点，就是说当前结点的右子树中的某个结点才是 p 和 q 的最小父结点，会被返回

 public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        
        if (root == null || root == p || root == q) {
            return root;
        }
        TreeNode left = lowestCommonAncestor(root.left, p, q);
         TreeNode right = lowestCommonAncestor(root.right, p, q);
       
        if (left == null && right == null) {
            return null;
        } else if (left == null) {
            return right;
        } else if (right == null) {
            return left;
        }else {
            return root;
        }
        
        
    }

235 Lowest Common Ancestor of a Binary Search Tree

Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
Output: 6
Explanation: The LCA of nodes 2 and 8 is 6.

这题跟上题唯一区别就是自上到下， 一个点如果夹在 pq 之间，那就是

这题跟上题唯一区别就是自上到下， 一个点如果夹在 pq 之间，那就是

所以根节点的值一直都是中间值，大于左子树的所有节点值，小于右子树的所有节点值，那么我们可以做如下的判断，如果根节点的值大于 p 和 q 之间的较大值，说明 p 和 q 都在左子树中，那么此时我们就进入根节点的左子节点继续递归，如果根节点小于 p 和 q 之间的较小值，说明 p 和 q 都在右子树中，那么此时我们就进入根节点的右子节点继续递归，如果都不是，则说明当前根节点就是最小共同父节点


public TreeNode lca(TreeNode root, int p, int q) {
   if (root == null) {
      return null;
    }
    int min = Math.min(p, q);
    int max = Math.max(p, q);
    
    if (root.key > max) {
      return lca(root.left, p, q);
    } else if (root.key < min) {
       return lca(root.right, p, q);
    } else {
      return root;
    }
  }



public TreeNode lca(TreeNode root, int p, int q) {
    int small = Math.min(p, q);
    int large = Math.max(p, q);
    while (root != null) {
      if (root.key < small) {
        root = root.right;
      } else if (root.key > large) {
        root = root.left;
      } else {
        return root;
      }
    }
    return null;
  }

450 delete node in BST

669 Trim a Binary Search Tree

如果要遍历全局，不用 return helper()之类的，那个是早点返回用的

Largest Number Smaller In Binary Sear

c

In a binary search tree, find the node containing the largest number smaller than the given target number.

If there is no such number, return -2^31.

Assumptions:

The given root is not null.
There are no duplicate keys in the binary search tree.
Examples

    5

  /    \

2      11

     /    \

    6     14

largest number smaller than 1 is Integer.MIN_VALUE(Java) or INT_MIN(c++)

largest number smaller than 10 is 6

largest number smaller than 6 is 5

返回上一个节点，所以要有个指针勾着

public int largestSmaller(TreeNode root, int target) {
    int res = Integer.MIN_VALUE;
    while (root != null) {
      if (root.key >= target) {
        root = root.left;
      } else {
        res = root;
        root.right;
      }
    }
    return res;
  }

Second Largest In Binary Search Tree

Find the second largest key in the given binary search tree.

If there does not exist the second largest key, return Integer.MIN_VALUE.

Assumptions:

The given binary search tree is not null.
Examples:

    2

  /   \

 1     4

      /

    3

the second largest key is 3.

分了三种情况，第一个是没有左子树，这时候 root 到了右节点这里，它的上一个 prev 节点就是答案；

有左子树，左子树没有右孩子了，我们为了答案统一，让 root 到了 左子树，prev 也到了这边， 也 return prev

左子树还有右孩子，那 root 就是一路往右边，直到尽头，prev 也是尽头，到了 root 这边， 然后返回 prev

 TreeNode prev = null;
    TreeNode curr = root;
    if(root == null || (root.right == null && root.left == null)) {
      return Integer.MIN_VALUE;
    }
    
    while(curr.right != null) {
      prev = curr;
      curr = curr.right;
    }
    //      2
    //   /     \
    // 1         4



    if(curr.left != null) {
      curr = curr.left;
    //      2
    //   /     \
    //  1        4
    //          /
    //          3


      while(curr.right != null) {
        curr = curr.right;
      }

    //      2
    //   /     \
    //  1        4
    //          /
    //          0
    //           \
    //            3


      prev = curr;
    }
    return prev.key;
  }

Kth Smallest Element in a

B

Given the root of a binary search tree, and an integer k, return the kth smallest value (1-indexed) of all the values of the nodes in the tree.

 

Example 1:


Input: root = [3,1,4,null,2], k = 1
Output: 1

暴力解法，就是把所有的值都放进 list， 里面用 list.get(k - 1) 就是了， 中序遍历

但是还有个方法就是直接返回 k 个

时间复杂度是 O h + O k,

空间复杂度是 OH

class Solution {
    int k, ans;
    public int kthSmallest(TreeNode root, int _k) {
        k = _k;
        dfs(root);
        return ans;
    }
    void dfs(TreeNode root) {
        if (root == null || k <= 0) return ;
        dfs(root.left);
        if (--k == 0) ans = root.val;
        dfs(root.right);
    }
}

Closest Number In Binary Search Tree II

In a binary search tree, find k nodes containing the closest numbers to the given target number. return them in sorted array

Assumptions:

The given root is not null.
There are no duplicate keys in the binary search tree.
Examples:

    5

  /    \

2      11

     /    \

    6     14

closest number to 4 is 5

closest number to 10 is 11

closest number to 6 is 6

 public int kthSmallest(TreeNode root, int k) {
        Deque<TreeNode> d = new ArrayDeque<>();
        while (root != null || !d.isEmpty()) {
            while (root != null) {
                d.addLast(root);
                root = root.left;
            }
            root = d.pollLast();
            if (--k == 0) return root.val;
            root = root.right;
        }
        return -1; // never
    }

O(log(n)+k)， 空间 O K

public int[] closestKValues(TreeNode root, double target, int k) {
    if (k < 0) {
        return new int[0];
    }
    Queue<Integer> q = new ArrayDeque<>(k);
    inOrder(root, q, target, k);
    int[] res = new int[q.size()];
    for (int i = 0; i < res.length; i++) {
      res[i] = q.poll();
    }
    return res;
  }

  private void inOrder(TreeNode root, Queue<Integer> q, double target, int k) {
    if (root == null) {
      return;
    }
    inOrder(root.left, q, target, k);
    if (q.size() < k) { // 无语啊，q.size = 0,的时候塞进去，用了等于就会多出来
      q.offer(root.key);
    } else if (Math.abs(root.key - target) < Math.abs(queue.peek() - target)) {
      queue.poll();
      queue.offer(root.key);
    } else {
      return;
    }
    inOrder(root.right, queue, target, k);
  }

另一个解法是用两个大小 stack， 遇到比 target 小的塞一边，大的塞一边，然后一个个对比 pop

最差 time O(N + K), 如果是 balance 的，那就是 O(K + lg N)

space On， 如果是 balance 的，那就是 O(n / 2), still On

public List<Integer> closestKValues(TreeNode root, double target, int k) {
    List<Integer> res = new ArrayList<>();
    Deque<Integer> pre = new ArrayDeque<>();
    Deque<Integer> suc= new ArrayDeque<>();
    this.traverseTreeInorder(root, target, pre);
    this.traverseTreeReverseInorder(root, target, suc);


    while (k > 0) {
        if (pre.empty()) {
            res.add(suc.pop());
        } else if (suc.empty()) {
            res.add(pre.pop());
        }else if (Math.abs(pre.peek() - target) < Math.abs(suc.peek() - target)) {
            res.add(pre.pop());
        } else {
            res.add(suc.pop());
        }
        k--;
    }
   
    return res;
  }

  private void traverseTreeInorder(TreeNode root, Deque<Integer> s, double target, int k) {
    if (root == null) {
      return;
    }
    this.traverseTreeInorder(root.left, target, s);
    // 提前return， 排斥比它大的， 剪枝
    if (root.val >= target) {
        return;
    }
    pre.push(root.val);
    this.traverseTreeInorder(root.right, target, s);
  }
private void traverseTreeReverseInorder(TreeNode root, Deque<Integer> l, double target, int k) {
     if (root == null) {
      return;
    }
    this.traverseTreeReverseInorder(root.right, target, l);
    // 提前return， 排斥比它小的， 剪枝
    if (root.val < target) {
        return;
    }
    pre.push(root.val);
    this.traverseTreeReverseInorder(root.left, target, l);
}