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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 |
/* 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; } |