walkingtospace

https://oj.leetcode.com/problems/validate-binary-search-tree/
 
 
/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}

walkingtospace

void quicksort(int input[], int left, int right) {
    if(left < right) {
        int pivot = input[right];
        int leftIt = left;
        int rightIt = right; 
        
        while(leftIt < rightIt) {
            while(input[leftIt] < pivot) leftIt++;
            while(input[rightIt] > pivot) rightIt--;
        

walkingtospace

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 * 
/*

walkingtospace

https://oj.leetcode.com/problems/evaluate-reverse-polish-notation/

/*
Evaluate the value of an arithmetic expression in Reverse Polish Notation.

Valid operators are +, -, *, /. Each operand may be an integer or another expression.

Some examples:
  ["2", "1", "+", "3", "*"] -> ((2 + 1) * 3) -> 9
  ["3", "3", "*"] -> ["9"]

walkingtospace

int findNeedle(int input[], int start, int end, int needle) {
    if(start > end) return -1;
    
    int mid = floor((start+end)/2);
    int result;
    
    if(input[mid] == needle) return mid;
    else if(input[mid] < needle) {
        result = findNeedle(input, mid+1, end, needle);
        if(result == -1) {

walkingtospace

//Given a list, rotate the list to the right by k places, where k is non-negative.

Node* rotateNode(Node* head, int k) {
 if( k<= 0) return head;
 
 Node* first = kth = head;
 Node* end = head;

 for(int i=0; i<k+1; i++) kth = kth->next;    
 

walkingtospace

/*
https://oj.leetcode.com/problems/populating-next-right-pointers-in-each-node/

차분히 생각해보면(대부분의 BST 문제는 recursive로 푼다), left->right는 right!=NULL 체크로 쉽게 연결할 수 있는데
right->parent's sibling's left 연결이 헷갈릴 수 있다.

key는 현재 자신의 sibling이 존재하는지 node는 알수없기 때문에 parent에서 children의 sibling이 존재하는지를 체크해줘서 연결해줘야
한다는 것을 눈치 채는 것.

첫번째시도 : 문제의 조건인 You may only use constant extra space 을 깜빡하고 recursive로 작성

walkingtospace

/* Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST. 
 
https://oj.leetcode.com/problems/convert-sorted-list-to-binary-search-tree/
 
[1,2,3,4,5]
     3
    /  \
   2    5  
  /    /
 1    4

walkingtospace

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
 

walkingtospace

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */