Polarcodes
BAN USERFor the solution, since the problem description says that all 1 are connected, it is not necessary to obtain leftObs[] and rightObs[] in the way described.
- Polarcodes February 16, 2015/* post order successor in binary tree
*/
#include<iostream>
using namespace std;
struct Node{
int data;
Node *left;
Node *right;
Node(int x): data(x), left(NULL), right(NULL) {}
};
Node *leftMostLeaf(Node *root){
while(root->left || root->right){
if(root->left) root = root->left;
else
root = root->right;
}
return root;
}
Node *postorderSuccessorRec(Node *root, int key, Node *parent, Node *treeroot){
//case 1: If current root is NULL, then succ is NULL
if(root == NULL)
return NULL;
//case 2: If current root is target node for which we are looking for successor
if(root->data == key){
//case 2.1: If current root is the root of the tree, succ is underfined.
if(root == treeroot)
return NULL;
//case 2.2: Otherwise, if current root is a right child, succ is parent.
else if(parent != NULL && parent->right == root)
return parent;
//case 2.3: otherwise current root is a left child and the following applies
//case 2.3.1: If the node has a right sibling, r, succ is the leftmost leaf in r's sub-tree
else if(parent != NULL && parent->left == root && parent->right != NULL)
return leftMostLeaf(parent->right);
//case 2.3.2: Otherwise succ is parent
else if(parent != NULL && parent->left == root && parent->right == NULL)
return parent;
//case 2.3.3: If none of above applies, then succ does not exist
else
return NULL;
}
//case 3: current root is not the target node for which we are looking successor
else{
//case 3.1: Search target node and its successor in left side of tree recursively, return if found
Node *left = postorderSuccessorRec(root->left, key, root, treeroot);
if(left)
return left;
//case 3.2: Search target node and its successor in right side of tree recursively, and return.
return postorderSuccessorRec(root->right, key, root, treeroot);
}
}
int main(){
Node *root = new Node(1);
root->left = new Node(2);
root->right = new Node(3);
root->left->left = new Node(4);
root->left->right = new Node(5);
root->right->left = new Node(6);
Node *succ;
succ = postorderSuccessorRec(root, 3, NULL, root);
cout<<succ->data<<endl;
}
This problem can be solved by dynamic programming.
Let the input be A[0, ..., n - 1] and target. Let the DP[n][100], where DP[i][j] means the minimal adjust sum for A[0], ..., A[i] with the requirement and the last element is j, i.e., A[i] = j, where 0 <=j <=100.
The recursive formula is DP[i][j] = min(DP[i-1][k] + | j- A[i]|), where j - target <= k < = j + target and k > =0. That is the previous adjustment sum can be DP[i-][k] and the current adjustment sum is |j - A[i]|, and we have to make sure j - target <= k <= j + target and k >=0.
The return value is ret = min DP[n-1][j] for 0 <= j <= 100.
For the inner loop why is for(j = k; j >=1; j--) instead of for(j = 1; j <=k; j++)?
- Polarcodes February 17, 2015