本文将介绍LeetCode285.InorderSuccessorinBST的详细情况，。我们将通过案例分析、数据研究等多种方式，帮助您更全面地了解这个主题，同时也将涉及一些关于113thLeetCo

本文将介绍LeetCode 285. Inorder Successor in BST的详细情况，。我们将通过案例分析、数据研究等多种方式，帮助您更全面地了解这个主题，同时也将涉及一些关于113th LeetCode Weekly Contest Reveal Cards In Increasing Order、19.3.5 [LeetCode 106] Construct Binary Tree from Inorder and Postorder Traversal、285. Inorder Successor in BST、Decred: The More Democratic Bitcoin Successor的知识。

• LeetCode 285. Inorder Successor in BST
• 113th LeetCode Weekly Contest Reveal Cards In Increasing Order
• 19.3.5 [LeetCode 106] Construct Binary Tree from Inorder and Postorder Traversal
• 285. Inorder Successor in BST
• Decred: The More Democratic Bitcoin Successor

LeetCode 285. Inorder Successor in BST

找中序遍历的后一个节点，那就中序遍历到当前节点后再往后一个，可以用递归，也可以非递归，完全没有用到BST的性质。

class Solution {
public:
    TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
        stack<TreeNode *> s;
        TreeNode *cur=root;
        bool flag=false;
        while (!s.empty() || cur!=NULL){
            while (cur){
                s.push(cur);
                cur = cur->left;
            }
            cur = s.top(); s.pop();
            if (flag) return cur;
            if (cur==p) flag=true;
            
            cur = cur->right;
        }
        return NULL;
    }
};

也可以充分利用BST的性质，如果p比当前节点小，说明在左子树，res=root；否则去右子树搜索。

class Solution {
public:
    TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
        TreeNode *res=NULL;
        while (root!=NULL){
            if (p->val<root->val){
                res = root;
                root = root->left;
            }else root = root->right;
        }
        return res;
    }
};

 用递归写

class Solution {
public:
    TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
        if (root==NULL) return NULL;
        if (p->val<root->val){
            TreeNode *left=inorderSuccessor(root->left,p);
            return left!=NULL?left:root;
        }else return inorderSuccessor(root->right,p);
    }
};

引申一下，如果求前面一个节点，也是一样做，只不过left right反一反。

113th LeetCode Weekly Contest Reveal Cards In Increasing Order

In a deck of cards, every card has a unique integer.  You can order the deck in any order you want.

Initially, all the cards start face down (unrevealed) in one deck.

Now, you do the following steps repeatedly, until all cards are revealed:

1. Take the top card of the deck, reveal it, and take it out of the deck.
2. If there are still cards in the deck, put the next top card of the deck at the bottom of the deck.
3. If there are still unrevealed cards, go back to step 1.  Otherwise, stop.

Return an ordering of the deck that would reveal the cards in increasing order.

The first entry in the answer is considered to be the top of the deck.

Input: [17,13,11,2,3,5,7]
Output: [2,13,3,11,5,17,7]
Explanation: 
We get the deck in the order [17,13,11,2,3,5,7] (this order doesn''t matter), and reorder it.
After reordering, the deck starts as [2,13,3,11,5,17,7], where 2 is the top of the deck.
We reveal 2, and move 13 to the bottom.  The deck is now [3,11,5,17,7,13].
We reveal 3, and move 11 to the bottom.  The deck is now [5,17,7,13,11].
We reveal 5, and move 17 to the bottom.  The deck is now [7,13,11,17].
We reveal 7, and move 13 to the bottom.  The deck is now [11,17,13].
We reveal 11, and move 17 to the bottom.  The deck is now [13,17].
We reveal 13, and move 17 to the bottom.  The deck is now [17].
We reveal 17.
Since all the cards revealed are in increasing order, the answer is correct.

class Solution {
public:
    vector<int> deckRevealedIncreasing(vector<int>& deck) {
        int s = deck.size();
        sort(deck.begin(),deck.end());
        if(s==1){
            return deck;
        }
        if(s==2){
            return deck;
        }
        vector<int> result;
        result.push_back(deck[s-2]);
        result.push_back(deck[s-1]);
        for(int i=s-3;i>=0;i--){
            
            
            int len = result.size();
            int last= result[len-1];
            result.insert(result.begin(),last);
            
            
            result.pop_back();
            result.insert(result.begin(),deck[i]);
            

        }
        return result;
    }
};

19.3.5 [LeetCode 106] Construct Binary Tree from Inorder and Postorder Traversal

Given inorder and postorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

For example, given

inorder = [9,3,15,20,7]
postorder = [9,15,7,20,3]

Return the following binary tree:

    3
   / \
  9  20
    /  \
   15   7

 1 class Solution {
 2 public:
 3     TreeNode*buildchild(vector<int>& postorder, vector<int>& inorder,int p1,int p2, int i1, int i2) {
 4         if (i2 < i1)
 5             return NULL;
 6         int nowroot = postorder[p2];
 7         TreeNode*ans = new TreeNode(nowroot);
 8         for (int i = i1; i <= i2; i++)
 9             if (inorder[i] == nowroot) {
10                 int left = i - i1, right = i2 - i;
11                 if (i != i1) 
12                     ans->left = buildchild(postorder, inorder,p1,p1+left-1, i1, i - 1);
13                 if (i != i2)
14                     ans->right = buildchild(postorder, inorder, p1 + left, p2 - 1, i + 1, i2);
15             }
16         return ans;
17     }
18     TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
19         return buildchild(postorder, inorder, 0,postorder.size()-1,0, inorder.size() - 1);
20     }
21 };

View Code

285. Inorder Successor in BST

Given a binary search tree and a node in it, find the in-order successor of that node in the BST.

Note: If the given node has no in-order successor in the tree, return null.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        if(root == null){
            return null;
        }
        if(p.right != null){ //右边不为空直接返回右边的最左个节点
            p = p.right;
            while(p.left != null){
                p = p.left;
            }
            return p;
        }else{
            TreeNode parent = null;
            while(root != p){
                if(root.val > p.val){
                    parent = root;//只有向左边走的时候才记录
                    root = root.left;
                }else{
                    root = root.right;
                }
            }
            return parent;
        }
    }
}

Decred: The More Democratic Bitcoin Successor

Decred, the token is DCR. The highlight of DCR is the integration of community governance into blockchain technology to initiate democratic voting on technical and non-technical changes through its blockchain-based voting system.

Specifically, DCR uses a mix of PoW and PoS to mine and reserve a portion of the DCR as a reward for developers developing new features in DCR software. Any DCR participant can propose new software features that are needed, and the community decides when to develop new features by voting. These new features can be developed and submitted by any programmer, and a certain amount of DCR can be paid for after passing. Therefore, DCR has created a self-sufficient, open collaboration, and evolving digital currency community.

Decred mining, first through the mining machine to deal with transactions to establish blocks, and through continuous collision search, find the number of computing targets that meet certain difficulty, and then spread to the network, PoW''s work is completed, to the mining process here Similar to Bitcoin, except that the block time is half of Bitcoin, about a block of 5 minutes. The mechanism for reaching consensus is different. Bitcoin relies on the nodes of the whole network to verify the block. Finally, the longest chain is the main chain. If the block mined out is valid in the main chain, it is the block. Therefore, whether the block is effective comes from almost the entire network consensus. The advantage of this is security, provided that there is no more than 51% of the power attack, the shortcoming is obvious inefficiency. The DCR introduces the PoS to vote to determine whether the newly mined blocks are valid. Each block only needs to randomly select 5 votes for voting. In the case where at least 3 votes pass, the block is recognized as valid and can be added. The rewards for successful verification of the block are 30 new DCR coins, which will be divided into 60% for PoW miners (a large portion for miners, so don’t cling to how to buy decred, try to mine decred as its reward is profit), 30% for PoS ballot holders, and the remaining 10% reserved for programmers involved in software development.

The specific mechanism of PoS is to lock a certain number of DCR purchase votes by the DCR holders. After the vote purchase, you need to wait for the miners to mine out. Each excavated block will contain up to 20 fresh votes. These votes need to wait until 256 new blocks are generated before they mature, that is, they have the right to vote. In order to encourage the miners to include fresh ballots in the excavated blocks, there will be an additional fee for purchasing the vote, which is reserved for the mine work. After maturity, if your vote is successfully selected to vote, the system will return the currency of the purchase and add rewards.

Decred''s mechanism improves the efficiency of the block, while ensuring security. The monetary reward reserved for the developer guarantees the development support of the software itself. Through the voting system, each decision is not affected by a few people. This formed an efficient, democratic community of PoW miners, PoS stakeholders and developers. In addition, Decred is also trying to establish a hierarchical decentralized autonomous regulatory organization to represent the different voices of the community. In this sense, Decred is a currency with a deeper social experimentation after Bitcoin currency.

Decred''s mechanism design solves some of the drawbacks of Bitcoin, and it has a fast iterative gene in the increasingly fierce competition of digital currency, which can quickly follow up to develop new features, so the decred prospects or decred value are worthy of optimism.

我们今天的关于LeetCode 285. Inorder Successor in BST的分享就到这里，谢谢您的阅读，如果想了解更多关于113th LeetCode Weekly Contest Reveal Cards In Increasing Order、19.3.5 [LeetCode 106] Construct Binary Tree from Inorder and Postorder Traversal、285. Inorder Successor in BST、Decred: The More Democratic Bitcoin Successor的相关信息，可以在本站进行搜索。