Category Archives: binary tree

find deepest node

Leave a reply

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

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

Leave a reply

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.

/* Copyleft: Ming Lin <minggr@gmail.com> */
/* http://www.careercup.com/question?id=5073112714444800 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "tree.h"

int sum(struct node *n)
{
	int left_sum;

	if (!n)
		return 0;

	left_sum = sum(n->left);

	if (n->left)
		n->data = left_sum;

	return n->data + left_sum + sum(n->right);
}

int main()
{
	struct node *root;
	int postorder[] = {1, 3, 5, 4, 2, 7, 10, 9, 8, 6};

	root = construct_bst(postorder, 0, 9);
	sum(root);

	print_tree(root);

	return 0;
}