| Algorithm

树形DP

树形DP简单来说即是父结点拿到子结点信息后，整合出自己的信息往上传递，信息不断复用。在解决这一类问题的时候，首先需要考虑可能性，左子树的可能性，右子树的可能性（或者所有子结点的可能性）以及加上当前结点后的可能性。根据这些可能性，列出向上传递过程中结点需要传递的信息有哪些，根据这些信息去构造一个结构/类returnData（囊括了数据成员和构造函数），在递归过程中我们需要考虑递归的终止条件，返回一个满足条件的基础returnData对象。

解决问题的代码大致分为三块：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void fun(node *head){ return process(head).mem;}

struct returnData(){};

returnData process(node *head){

	//递归终止条件

	//考虑可能性

process(head->left);

process(head->right);

//整合子结点信息为head的信息返回

return returnData(...);

}

例题

  • Q1: 判断平衡二叉树 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
struct returnData {
	returnData(int a, bool b) : height(a), isB(b){}
	int height;
	bool isB;
};
//返回以head为头的子树，高度值和是否平衡的信息
returnData process(node *head) {
	if (head == NULL) {
		return returnData(0, true);
	}
	returnData left = process(head->left);
	returnData right = process(head->right);
	if (!left.isB || !right.isB)
		return returnData(0, false);
	else if (abs(left.height - right.height) > 1)
		return returnData(-1, false);
	else return returnData(max(left.height,right.height) + 1, true);//在从底向上的过程中将新的信息保存记录下来再返回给上级
}
bool isBT(node *head) {
	return process(head).isB;
}

复杂度为O(n)

  • Q2: 判断一棵二叉树的结点的最远距离
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int maxDist(node *head) {
	return process2(head).maxDist ;
}

struct returnData2 {
	int height;
	int maxDist;
	returnData2(int h, int m) : height(h), maxDist(m){}
};
//以head为头的最远距离和高度信息
returnData2 process2(node *head) {
	if (head == NULL) {
		return returnData2(0, 0);
	}
	returnData2 left = process2(head->left);
	returnData2 right = process2(head->right);
	int p1 = left.maxDist;//maxDis在左子树上
	int p2 = right.maxDist;//maxDist在右子树上
	int p3 = left.height + right.height + 1;//从左子树离head最远的结点到右子树到head最远的结点的距离
	int h = max(left.height, right.height) + 1;
	int m =  max(max(p1, p2),p3);
	return returnData2(h, m);
}
  • Q3: 判断一棵树的最大搜索二叉子树的大小
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
int maxSearchTreeSize(node *head) {
	return process4(head).maxSearchSize;
}

struct returnData4 {
	int maxSearchSize;
	bool isAllSearch;
	int max;
	int min;
	returnData4(int maxSearchSize, bool isAllSearch, int max, int min)
		:maxSearchSize(maxSearchSize), isAllSearch(isAllSearch), max(max), min(min){}
};
returnData4 process4(node *head) {
	if (head == NULL)
		return returnData4(0, true, INT_MIN, INT_MAX);
	returnData4 leftData = process4(head->left);
	returnData4 rightData = process4(head->right);
	int p1 = leftData.maxSearchSize;
	int p2 = rightData.maxSearchSize;
	int p3 = INT_MIN;
	if (leftData.isAllSearch && 
		rightData.isAllSearch && 
		head->val > leftData.max 
		&& head->val < rightData.min) {
		p3 = p1 + p2 + 1;
	}
	int maxSearchSize = max(max(p1, p2), p3);
	bool isAllSearch = (p3 == maxSearchSize) ? true : false;
	int maxm = max(max(leftData.max, rightData.max), head->val);
	int minm = min(min(leftData.min, rightData.min), head->val);
	return returnData4(maxSearchSize, isAllSearch, maxm, minm);
}

  • Q4: 员工聚会问题

    1533029493243

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
struct employee{
	int huo;
	list<employee> nexts;//该员工的下属列表
	employee(int huo) : huo(huo) {}
	//employee &operator=(employee &e) { return e; }
};
int getMaxhuo(employee boss) {
	returnData5 data = process5(boss);
	return max(data.lai_huo, data.bu_lai_huo);
}
//递归向上传递信息体
struct returnData5 {
	int lai_huo;
	int bu_lai_huo;
	returnData5(int lai_huo, int bu_lai_huo) : lai_huo(lai_huo), bu_lai_huo(bu_lai_huo){}
};
//（考虑可能性，左树，右树，每个孩子，再加上自己）以boss为头的整棵子树得到boss来时最大活跃度，boss不来时最大活跃度
returnData5 process5(const employee &boss) {
	if (boss.nexts.empty()) {
		return returnData5(boss.huo, 0);
	}
	int lai_huo = boss.huo;
	int bu_lai_huo = 0;
	for (auto it = boss.nexts.begin(); it != boss.nexts.end(); it++) {
		lai_huo += process5(*it).bu_lai_huo;//boss来，员工都不来
		bu_lai_huo += max(process5(*it).lai_huo, process5(*it).bu_lai_huo);//boss不来，员工爱来不来，取最大的
	}
	return returnData5(lai_huo, bu_lai_huo);
}

题目和图片取自《左程云的算法进阶班》

ESC