**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; }