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