Category Archives: binary tree

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.