Binary Search Tree

tags: Monotonic Stack,LeetCode101,Binary Search Tree Mono-descreasing stack Key: The largest number is the root, that we can observe in by iteration. We must clear the stack to fill the right side of BST after loop. The last popped element is the left of current node. From top to bottom, the top element is the right side of the element that under the top. class Solution { public: TreeNode* constructMaximumBinaryTree(vector<int>& nums) { vector<TreeNode*> res(nums....

tags: Binary Search Tree,Binary Tree,Tree

tags: Binary Search Tree, AVL Tree,Tree

tags: Algorithm,Data Structures,Binary Search Tree 分为三种：前序、后序和中序，其中最容易用栈改写的是后序。 前序(Preorder)：Root -> Left -> Right class Solution { public: void processPreorderTraversal(TreeNode* root, vector<int> & collector) { if (root == nullptr) { return; } processPreorderTraversal(root->left, collector); collector.push_back(root->val); processPreorderTraversal(root->right, collector); } vector<int> inorderTraversal(TreeNode* root) { vector<int> ret; if (root == nullptr) { return ret; } processPreorderTraversal(root, ret); return ret; } }; 中序(Inorder): Left -> Root -> Right class Solution { public: void processInorderTraversal(TreeNode* root, vector<int> & collector) { if (root == nullptr) { return; } processInorderTraversal(root->left, collector); collector....