Monthly Archives: September 2014

binary tree top-down recursion: is_bst()

Leave a reply

判断binary tree是不是binary search tree

如何定义递归式？
int is_bst(struct node *n, int min, int max);
子树n的所有节点必需满足min < n->data < max，不断更新min/max值，以深度优先搜索形式从上往下传递 

/* Copyleft: Ming Lin <minggr@gmail.com> */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#include “tree.h”

int check_bst(struct node *n, int min, int max)
{
	if (!n)
		return 1;

	if (n->data < min || n->data > max)
		return 0;

	return check_bst(n->left, min, n->data) &&
		check_bst(n->right, n->data, max);
}

int main()
{
	struct node *root;
	int postorder[] = {5,7,6,9,11,10,8};

	root = construct_bst(postorder, 0, 6);
	printf(“check_bst: %d\n”, check_bst(root, INT_MIN, INT_MAX));
	root->data = 100;
	printf(“check_bst: %d\n”, check_bst(root, INT_MIN, INT_MAX));

	return 0;
}

find deepest node

Leave a reply

http://www.careercup.com/question?id=5738278644875264

Find the deepest node in a binary tree:
Example:

A
/ \
B C
/ \ / \
D E F G
\
H

Return Node ‘H’

如何定义递归原型?
void find_deepest(struct node *n, int cur_depth, int *deepest, struct node **deepest_node)
按深度优先，将depth从上往下传递，更新deepest depth

关键要能够想到就是要遍历每个节点，不断更新deepest depth，按深度优先去遍历能够方便地知道当前node的depth，也就是parent node depth + 1

这种top-down传递信息的递归，并不是要用子问题的解去构造父问题的解。

/* Copyleft: Ming Lin <minggr@gmail.com> */
/* http://www.careercup.com/question?id=5738278644875264 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "tree.h"

void find_deepest(struct node *n, int cur_depth, int *deepest, struct node **deepest_node)
{
	if (!n)
		return;

	if (cur_depth > *deepest) {
		*deepest = cur_depth;
		*deepest_node = n;
	}

	find_deepest(n->left, cur_depth + 1, deepest, deepest_node);
	find_deepest(n->right, cur_depth + 1, deepest, deepest_node);
}

struct node *solve(struct node *root)
{
	int deepest;
	struct node *deepest_node;

	deepest = 0;
	find_deepest(root, 1, &deepest, &deepest_node);

	return deepest_node;
}

int main()
{
	struct node *root;
	struct node *deepest;
	int postorder[] = {10, 20, 50, 40, 70, 60, 30};

	root = construct_bst(postorder, 0, 6);
	deepest = solve(root);
	printf("deepest: %d\n", deepest->data);

	return 0;
}

update node with sum of it’s left sub-tree

Leave a reply

1. 思维完整性

需要更新所有的结点，必定是tree traversal: pre-order/in-order/post-order

2. 正确定义递归原型

f(n)定义为sum of sub-tree n
n->data = f(n->left)
f(n) = n->data + f(n->left) + f(n->right)

traversal node in post-order.

/* Copyleft: Ming Lin <minggr@gmail.com> */
/* http://www.careercup.com/question?id=5073112714444800 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "tree.h"

int sum(struct node *n)
{
	int left_sum;

	if (!n)
		return 0;

	left_sum = sum(n->left);

	if (n->left)
		n->data = left_sum;

	return n->data + left_sum + sum(n->right);
}

int main()
{
	struct node *root;
	int postorder[] = {1, 3, 5, 4, 2, 7, 10, 9, 8, 6};

	root = construct_bst(postorder, 0, 9);
	sum(root);

	print_tree(root);

	return 0;
}

 

make string a postfix notation

Leave a reply

Imagine x is an operand and * is a binary operator. We say a string of x and * follows Reverse Polish notation if it is a postfix notation. 

For example strings xx*, x, and xx*xx** follow Reverse Polish notation. 

Given a string of x and *, how many insert, delete, and replace operations are needed to make the string follow the RPN. 

For example, xx* need 0 operation to follow RPN since it already follows RPN. 
x*x needs two operations to become xx* which follows RPN. 
*xx* needs one operation to become xx* which follows RPN. 

Your algorithm should work for a string of size up to 100.

/* Copyleft: Ming Lin <minggr@gmail.com> */
/* http://www.careercup.com/question?id=5762415492857856 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

#define MAX 300
int cache[MAX][MAX];

int postfix(char *expr, int i, int j)
{
	char c = expr[j];
	int min;
	int tmp;
	int k;

	if (cache[i][j] != -1)
		return cache[i][j];

	if (i == j) {
		if (expr[i] == '*') {
			cache[i][j] = 1;
			return cache[i][j];
		} else {
			cache[i][j] = 0;
			return cache[i][j];
		}
	}

	// why need?
	if (i + 1 == j) {
		if (expr[i] == '*' && expr[j] == '*') {
			cache[i][j] = 2;
			return cache[i][j];
		}
		if (expr[i] == '*' && expr[j] == 'X') {
			cache[i][j] = 1;
			return cache[i][j];
		}
		if (expr[i] == 'X' && expr[j] == '*') {
			cache[i][j] = 1;
			return cache[i][j];
		}
		if (expr[i] == 'X' && expr[j] == 'X') {
			cache[i][j] = 1;
			return cache[i][j];
		}
	}

	min = INT_MAX;
	if (c == '*') {
		for (k = i; k <= j-2; k++) {
			tmp = postfix(expr, i, k) + postfix(expr, k+1, j-1);
			if (tmp < min)
				min = tmp;
		}
	} else {
		//replace 'X' with '*'
		for (k = i; k <= j-2; k++) {
			tmp = postfix(expr, i, k) + postfix(expr, k+1, j-1) + 1;
			if (tmp < min)
				min = tmp;
		}

		//delete 'X'
		tmp = postfix(expr, i, j-1) + 1;
		if (tmp < min)
			min = tmp;

		//add '*'
		for (k = i; k <= j-1; k++) {
			tmp = postfix(expr, i, k) + postfix(expr, k+1, j) + 1;
			if (tmp < min)
				min = tmp;
		}
	}

	cache[i][j] = min;
	return cache[i][j];
}

void init_cache(void)
{
	int i, j;

	for (i = 0; i < MAX; i++)
		for (j = 0; j < MAX; j++)
			cache[i][j] = -1;
}

int main()
{
	char expr[MAX];
	int j;

	init_cache();
	
	while (1) {
		scanf("%s", expr);
		j = strlen(expr) - 1;
		printf("%d\n", postfix(expr, 0, j));
	}
	return 0;
}