Daily question brushing record (VIII)

The first question is : The finger of the sword Offer II 052. Flatten the binary search tree

LeetCode: The finger of the sword Offer II 052. Flatten the binary search tree
describe :
Here's a binary search tree , please Traverse in middle order Rearrange it into an incremental sequential search tree , Make the leftmost node in the tree the root node of the tree , And each node has no left child , There is only one right child node .

Their thinking :

• Traverse in the middle order , Left -> root -> Right
• Let the right node of a node point to the traversed node
• The nodes traversed by the loop point to the right node
• Finally, return to the next node of the node
  

Code implementation :

class Solution {
    
	//  Give Way pre.next Indicates the header node 
    private TreeNode pre = new TreeNode();
    //  Give Way tmp To point to the operation of adding nodes 
    private TreeNode tmp = pre;
    public TreeNode increasingBST(TreeNode root) {
    
        if(root == null) return null;
        increasingBST(root.left);
        tmp.right = new TreeNode(root.val);
        tmp = tmp.right;
        increasingBST(root.right);
        return pre.right;
    }
}

The second question is : The finger of the sword Offer II 053. Middle order successor in binary search tree

LeetCode: The finger of the sword Offer II 053. Middle order successor in binary search tree
describe :
Given a binary search tree and one of its nodes p , Find the sequential successor of this node in the tree . If the node has no middle order successor , Please return null .

node p The following is the value ratio p.val The node with the smallest key value among the large nodes , That is, the order nodes traversed in the middle order p The next node of .

Their thinking :

• Cycle until root It's empty .
• If at present root.val > p.val, Then it can only be in the left tree , Because the values of the nodes of the right subtree of the binary search tree are greater than the values of the nodes of the left subtree . Record the node . And then let root = root.left
• If at present root.val < p.val, Then look for it from the right tree . Give Way root = root.right
  

Code implementation :

class Solution {
    
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
    
        TreeNode ans = null;
        while(root != null) {
    
        	// root.val > p.val  There is no need to take the right subtree to find ,  The right side will only be bigger 
            if(root.val > p.val){
    
            	//  Every time ,  The final ans Is the last required node 
                ans = root;
                root = root.left;
            }else{
    
                root = root.right;
            }
        }
        return ans;
    }
}

Third question : The finger of the sword Offer II 054. Sum of all values greater than or equal to nodes

LeetCode: The finger of the sword Offer II 054. Sum of all values greater than or equal to nodes

describe :
Given a binary search tree , Please replace the value of each node with the sum of all node values greater than or equal to the node value in the tree .

As a reminder , The binary search tree satisfies the following constraints ：

• The left subtree of a node contains only the key Less than Node key node .
• The right subtree of a node contains only the key Greater than Node key node .
• Left and right subtrees must also be binary search trees .
  
  

Their thinking :

• Here is the idea of traversal in middle order , But here we use Right -> root -> Left Methods
• Add up the values of the nodes each time . Then replace the value of the node root.val += sumsum=root.val
  

Code implementation :

class Solution {
    
    private int sum = 0;
    public TreeNode convertBST(TreeNode root) {
    
        if(root == null) return null;
        convertBST(root.right);
        //  Modify the value of this node 
        root.val += sum;
        sum = root.val;
        convertBST(root.left);
        return root;
    }
}

Fourth question : The finger of the sword Offer II 055. Binary search tree iterator

LeetCode: The finger of the sword Offer II 055. Binary search tree iterator

describe :
Implement a binary search tree iterator class BSTIterator , Represents a binary search tree traversed in middle order （BST） The iterator ：

• BSTIterator(TreeNode root) initialization BSTIterator An object of class .BST The root node root Will be given as part of the constructor . The pointer should be initialized to a value that does not exist in BST Number in , And the number is less than BST Any element in .
• boolean hasNext() If there is a number traversing to the right of the pointer , Then return to true ; Otherwise return to false .
• int next() Move the pointer to the right , Then return the number at the pointer .
  Be careful , The pointer is initialized to a value that does not exist in BST Number in , So for next() The first call of will return BST The smallest element in .

It can be assumed next() The call is always valid , in other words , When calling next() when ,BST There is at least one next number in the middle order traversal of .

Their thinking :

1. When initializing , Set nodes to In the sequence traversal The method is stored in list in
2. next() When , return index++ The value of the node index For the initial 0
3. hasNext() When , as long as index!<list.size() Namely true, The opposite is false

Code implementation :

class BSTIterator {
    
    private List<Integer> list = new ArrayList<>();
    private int index = 0;
    public BSTIterator(TreeNode root) {
    
        inorderBST(root);
    }
    public TreeNode inorderBST(TreeNode root) {
    
        if(root == null) return null;
        inorderBST(root.left);
        list.add(root.val);
        inorderBST(root.right);
        return root;
    }
    
    public int next() {
    
        return list.get(index++);
    }
    
    public boolean hasNext() {
    
        if(index < list.size()) {
    
            return true;
        }else{
    
            return false;
        }
    }
}

Fifth question : The finger of the sword Offer II 056. The sum of two nodes in a binary search tree

LeetCode: The finger of the sword Offer II 056. The sum of two nodes in a binary search tree

describe :
Given a binary search tree The root node root And an integer k , Please judge whether there are two nodes in the binary search tree, and the sum of their values is equal to k . Suppose that the values of nodes in the binary search tree are unique .

Their thinking :

• What we use here is Hashtable Ideas
• For the value of the current node root.val We can judge k - root.val Whether it exists in the hash table .
  • If there is , Then the sum of the two nodes is k
  • If it doesn't exist , Then add the value of this node to In the hash table

Code implementation :

class Solution {
    
    private Set<Integer> set = new HashSet<>();
    public boolean findTarget(TreeNode root, int k) {
    
        if(root == null) return false;
        //  If  k-root.val  Value   There is ,  Just go back to true;
        if(set.contains(k-root.val)) return true;
        //  If   non-existent ,  Add to   On the hash table .
        set.add(root.val);
        return findTarget(root.left,k) || findTarget(root.right,k);
    }
}

Sixth question : The finger of the sword Offer II 059. The second of data flow K Big numbers

LeetCode: The finger of the sword Offer II 059. The second of data flow K Big numbers

describe :
Design a data stream to find the k Classes of large elements （class）. Note that it's the... After the order k Big element , Not the first k A different element .

Please implement KthLargest class ：

• KthLargest(int k, int[] nums) Use integers k And integer stream nums Initialize object .
• int add(int val) take val Insert data stream nums after , Returns the current data stream at k Big elements .
  

Their thinking :

• Use here Priority queue , To add .
• When initializing , Start a priority queue The size is k Of Heap , And then nums Array is added to the priority queue .
• add During operation ,
  • If the current queue is not full , Just join the team , If the full ,
  • Determine the current team top element , Is it less than the inserted value , If it is less than , Pop up top element , Then join the team

Code implementation :

class KthLargest {
    
    private int k;
    private PriorityQueue<Integer> pq;
    public KthLargest(int k, int[] nums) {
    
        this.k = k;
        pq = new PriorityQueue<>(k,(o1,o2)->(o1-o2));
        for(int num : nums) {
    
            add(num);
        }
    }
    
    public int add(int val) {
    
        if(pq.size() < k) {
    
            pq.offer(val);
        }else{
    
            if(val > pq.peek()) {
    
                pq.poll();
                pq.offer(val);
            }
        }
        return pq.peek();
    }
}