“This is the 13th day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021”

A search in a binary search tree

The title

Given the root node of a binary search tree (BST) and a value. You need to find nodes in BST that have a value equal to the given value. Returns the subtree rooted with this node. If the node does not exist, NULL is returned.

Their thinking

Binary search tree is an ordered tree, which has the following characteristics:

  1. The values of all nodes in the left subtree are less than the values of the root node;
  2. The values of all nodes in the right subtree are greater than the values of the root node;

So we can solve this recursively.

Code implementation

class Solution {
    // Recursive, using binary search tree features
    public TreeNode searchBST(TreeNode root, int val) {
        if (root == null || root.val == val) {
            return root;
        }
        // If less than the root node
        if (val < root.val) {
            return searchBST(root.left, val);
        } else {
        / / and vice
            returnsearchBST(root.right, val); }}}Copy the code

Time complexity: O(H), H is the height of the binary search tree.

Space complexity: O(H), depth of recursive stack is H.

It’s not a binary search tree

The title

Given a binary tree, determine whether it is a valid binary search tree.

Their thinking

Binary search tree has one characteristic: in the middle order traversal, the value of the output binary search tree node is an ordered sequence.

Therefore, we can judge whether the sequence is orderly by means of middle order traversal, and thus determine whether the binary tree is an effective binary tree.

Code implementation

/** * 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 long pre = Long.MIN_VALUE;
    public boolean isValidBST(TreeNode root) {
        if (root == null) {
            return true;
        }

        if(! isValidBST(root.left)){return false;
        }
        if (root.val <= pre) {
            return false;
        }
        pre = root.val;
        returnisValidBST(root.right); }}Copy the code

Time complexity: O(n), where N is the number of nodes in the binary tree.

Space complexity: O(n), where N is the number of nodes in the binary tree;

Find the minimum absolute difference of binary search tree

The title

You are given a binary search tree in which all nodes are non-negative. Compute the minimum absolute value of the difference between any two nodes in the tree.

Their thinking

Because a binary search tree is an ordered tree, by traversing the middle order, we can get an ordered array, which translates to maximizing the value in an ordered array.

Code implementation

/** * 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 {
    int ans;
    int pre;
    public int getMinimumDifference(TreeNode root) {
        ans = Integer.MAX_VALUE;
        pre = -1;
        inOrder(root);
        return ans;
    }

    public void inOrder(TreeNode node){
        if (node == null) {
            return;
        }
        inOrder(node.left);
        if (pre == -1) {
            pre = node.val;
        } else{ ans = Math.min(ans, node.val - pre); pre = node.val; } inOrder(node.right); }}Copy the code

Time complexity: O(n), where N is the number of nodes in the binary search tree.

Space complexity: O(n), the depth of the recursive stack is the number of nodes N.

Find the mode of a binary search tree

The title

Given a binary search tree (BST) with the same value, find all the modes (the element with the highest frequency) in the BST.

Their thinking

  1. The binary search tree is traversed in order, and an ordered array is obtained.
  2. Hash table is used to store the number of occurrences of each element in an ordered array, and record the highest number of values maxLen;
  3. Through the hash table, the set of elements with the highest frequency is obtained according to maxLen;

Code implementation

/** * 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 {
    private List<Integer> list;
    public int[] findMode(TreeNode root) {
        list = new ArrayList();
        inOrder(root);

        Map<Integer, Integer> map = new HashMap();
        int maxLen = Integer.MIN_VALUE;
        for (int value :list) {
            map.put(value, map.getOrDefault(value, 0) + 1);
            if(maxLen < map.get(value)) { maxLen = map.get(value); }}if (maxLen > 0) {
            List<Integer> ans = new ArrayList<>();
            for (int b:map.keySet()) {
                if(map.get(b).equals(maxLen)) { ans.add(b); }}int answ[] = new int[ans.size()];
            for (int i = 0; i < ans.size(); i++) {
                answ[i] = ans.get(i);
            }
            return answ;
        }

        return new int[0];
    }

    public void inOrder(TreeNode node){
        if (node == null) return; inOrder(node.left); list.add(node.val); inOrder(node.right); }}Copy the code

Time complexity: O(n), the complexity of traversing the tree.

Space complexity: O(n), the space cost of recursive stack space.

The last

Well, that’s the end of the binary search tree. I believe that after reading this article, you will have a certain understanding of binary search tree properties, thank you for reading.

Previous articles:

  • StoreKit2 smells this good? Yeah, I tried it. It smells good
  • After reading this article, I am no longer afraid of being asked how to construct a binary tree.
  • The game guys are trying to get people to pay again. That’s bad!
  • Take you rolled a netease holding cloud music home | adapter
  • Netease Cloud Music Home Page (3)
  • Netease Cloud Music Home Page (2)
  • Netease Cloud Music Home Page (a)
  • Does the code need comments? Write and you lose
  • I would not study in Codable for a long time. They are for fun
  • IOS handles web data gracefully. Do you really? Why don’t you read this one
  • UICollectionView custom layout! This one is enough

Please drink a cup ☕️ + attention oh ~

  1. After reading, remember to give me a thumbs-up oh, there is 👍 power
  2. Follow the public number – HelloWorld Jie Shao, the first time push new posture

Finally, creation is not easy, if it is helpful to you, I hope you can praise and support, what questions can also be discussed in the comments section 😄 ~