No. 46 – Nodes with Sum in a Binary Search Tree

Problem: Given a binary search tree, please check whether there are two nodes in it whose sum equals a given value.

参考:http://codercareer.blogspot.com/2013/03/no-46-nodes-with-sum-in-binary-search.html

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

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

struct stack {
	struct node **s;
	int top;
};

struct stack *stack_l, *stack_r;

struct node *most_left(struct node *root)
{
	struct node *n = root;

	while (n) {
		stack_l->s[stack_l->top++] = n;
		n = n->left;	
	}

	return n;
}

struct node *most_right(struct node *root)
{
	struct node *n = root;

	while (n) {
		stack_r->s[stack_r->top++] = n;
		n = n->right;	
	}

	return n;
}

int height(struct node *root)
{
	int l, r;

	if (!root)
		return 0;

	l = height(root->left);
	r = height(root->right);

	if (l > r)
		return l+1;
	else
		return r+1;
}

void init_stack(struct node *root)
{
	int h = height(root);

	stack_l = malloc(sizeof(struct stack));
	stack_r = malloc(sizeof(struct stack));
	stack_l->s = malloc(h * sizeof(struct node *));
	stack_r->s = malloc(h * sizeof(struct node *));
	stack_l->top = stack_r->top = 0;

	most_left(root);
	most_right(root);
}

struct node *next(struct stack *s)
{
	struct node *n;

	n = s->s[s->top-1];
	s->top--;

	n = n->right;
	while (n) {
		s->s[s->top++] = n;
		n = n->left;
	}

	if (s->top == 0)
		return NULL;
	else
		return s->s[s->top-1];
}

struct node *prev(struct stack *s)
{
	struct node *n;

	n = s->s[s->top-1];
	s->top--;

	n = n->left;
	while (n) {
		s->s[s->top++] = n;
		n = n->right;
	}

	if (s->top == 0)
		return NULL;
	else
		return s->s[s->top-1];
}

void print_next(struct stack *s)
{
	struct node *n;

	n = s->s[s->top - 1];
	do {
		printf("%d ", n->data); 
	} while (n = next(s));
	printf("\n");
}

void print_prev(struct stack *s)
{
	struct node *n;

	n = s->s[s->top - 1];
	do {
		printf("%d ", n->data); 
	} while (n = prev(s));
	printf("\n");
}

void sum(struct stack *ls, struct stack *rs, int k)
{
	struct node *ln, *rn;

	ln = ls->s[ls->top-1];
	rn = rs->s[rs->top-1];

	while (ln != rn) {
		if (ln->data + rn->data == k) {
			printf("key %d: %d + %d\n", k, ln->data, rn->data);
			break;
		}

		if (ln->data + rn->data > k)
			rn = prev(rs);
		else
			ln = next(ls);
	}

	if (ln == rn)
		printf("key %d: sum not found\n", k);
}

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

	root = construct_bst(postorder, 0, n-1);

	print_tree(root);
	printf("\n");
	init_stack(root);
	//print_next(stack_l);
	//print_prev(stack_r);

	key = 22;
	sum(stack_l, stack_r, key);

	return 0;
}

 

Leave a Reply