Monthly Archives: September 2014

binary tree top-down recursion: is_bst()

判断binary tree是不是binary search tree

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

find deepest node

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传递信息的递归,并不是要用子问题的解去构造父问题的解。

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

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.

 

make string a postfix notation

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.