Posts

Showing posts with the label Divide and conquer

878. Boundary of Binary Tree

/** * Definition of TreeNode: * class TreeNode { * public: * int val; * TreeNode *left, *right; * TreeNode(int val) { * this->val = val; * this->left = this->right = NULL; * } * } */ class Solution { public : /** * @param root: a TreeNode * @return: a list of integer */ vector < int > boundaryOfBinaryTree(TreeNode * root) { // write your code here vector < int > res; if (root == NULL ){ return res; } vector < int > left; //findLeftBoundary(root->left, left); TreeNode *copy = root->left; //这种方法是左右两边边界最后一个会没有取到,最后连起来时,leaves已经包括了,不需要再去重复了。 //这个题开始没有搞出来的原因是,处理left,right时没有从left和right node开始,而是从root开始的,没有分治啊,一定严格分治思想!!!!!! if (copy != NULL ){ while (!(copy->left == NULL && copy->right == NULL )){ left.push_back(copy->val); if (copy->left != NUL...

1188. Minimum Absolute Difference in BST

Description 中文 English Given a binary search tree with non-negative values, find the minimum  absolute difference  between values of any two nodes. There are at least two nodes in this BST. Have you met this question in a real interview?    Yes Problem Correction Example Input: 1 \ 3 / 2 Output: 1 Explanation: The minimum absolute difference is 1, which is the difference between 2 and 1 (or between 2 and 3). int getMinimumDifference (TreeNode * root) { // Write your code here // find the max value among values smaller than root->val; // find the min value among values larger than root->val; int diff = INT_MAX; if (root->left != NULL ){ TreeNode * temp = root->left; while (temp->right != NULL ){ temp = temp->right; } diff = min(diff, abs (root->val - temp->val)); //先...

73. Construct Binary Tree from Preorder and Inorder Traversal

class Solution { public : /** * @param inorder: A list of integers that inorder traversal of a tree * @param postorder: A list of integers that postorder traversal of a tree * @return: Root of a tree */ unordered_map < int , int > mp; TreeNode * buildTree ( vector < int > &preorder, vector < int > &inorder) { // write your code here // preorder: 根左右 // inorder: 左根右 // 根据preoder中的根,找到inorder中position, then the left side is the left substree, the right side is the right substree // recursion TreeNode *res; int sizeN = preorder.size(); if (sizeN == 0 ){ return NULL ; } for ( int i = 0 ; i < sizeN; i++){ mp[inorder[i]] = i; } return build(preorder, 0 , preorder.size() - 1 , inorder, 0 , inorder.size() - 1 ); } TreeNode * build ( vector < int > &preorder, int...

106. Convert Sorted List to Binary Search Tree

class Solution { public : /* * @param head: The first node of linked list. * @return: a tree node */ TreeNode * sortedListToBST (ListNode * head) { // write your code here // Divide and conquer //1, slow and fast pointers finding the mid //2, pick the middle as root node //3, Divide //4, conquer if (head == NULL ){ return NULL ; } if (head->next == NULL ){ TreeNode *root = new TreeNode(head->val); return root; } ListNode *dummy = new ListNode( 0 ); dummy->next = head; ListNode *copy = head; ListNode *slow = head; ListNode *fast = head->next; ListNode *pre = dummy; while (fast != NULL && fast->next != NULL ){ pre = slow; slow = slow->next; fast = fast->next->next; } pre->next = NULL...