在上节的基础上，本节我们将继续汇总一些 LeetCode 有关二叉树的题。
接着上节，我们还是使用之前的程序框架，可以手动输入样例并测试，解题的方法不唯一。
所有题均来自于leetcode。
不同的二叉搜索树
给定一个整数 n，求以 1 ... n 为节点组成的二叉搜索树有多少种？
图片.png
这是一个动态规划的题，每一个根节点都是由它的左子树和右子树组成的，如果根节点是 i，那左子树就是(1,2,..,i-1)，而右子树就是(i+1,i+2,...,n)，那么根节点的情况就是两个子树情况的乘积了，考虑所有的节点情况求和即可。
具体程序如下:
// 96 不同的二叉搜索树
int numTrees(int n) {
vector<int> data(n+1,0);
data[0]=1;
data[1]=1;
for(int i=2;i<=n;i++){
for(int j=1;j<=i;j++){
data[i]+=data[j-1]*data[i-j];
}
}
return data[n];
}
测试程序：
int main(){
//test
//cout<<"test:......"<<endl;
int n;
cin>>n;
cout<<numTrees(n)<<endl;
return 0;
}
测试结果：
3
5
二叉树中的最大路径和
给定一个非空二叉树，返回其最大路径和。
本题中，路径被定义为一条从树中任意节点出发，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。
图片.png
先考虑普遍的一种情况，对于一个非空根节点，无非有三种路径：
- 左子树+根节点+右子树
- 左子树+根节点+根节点的父节点
- 根节点+右子树+根节点的父节点
根节点是必经之路，我们要选出最大的路径，一方面三种路径间择优，另一方面节点与0间择优。
具体程序如下：
// 124 二叉树中的最大路径和
int maxPathSum_helper(BiTree root,int &val_){
if(root == nullptr){
return 0;
}
int left_ = maxPathSum_helper(root->left,val_);
int right_ = maxPathSum_helper(root->right,val_);
int path1 = stoi(root->val) + max(0,left_) + max(0,right_);
int path2 = stoi(root->val) + max(0,max(left_,right_));
val_ = max(val_,max(path1,path2));
return path2;
}
int maxPathSum(BiTree root){
int val = INT_MIN;
maxPathSum_helper(root,val);
return val;
}
测试程序：
int main(){
//test
//cout<<"test:......"<<endl;
BiTree tree = levelCreate();
cout<<maxPathSum(tree)<<endl;
return 0;
}
测试结果：
1
2 3
# # # #
6
-10
9 20
# # 15 7
# # # #
42
二叉树的前序遍历
给定一个二叉树，返回它的前序遍历。
图片.png
进阶: 递归算法很简单，你可以通过迭代算法完成吗？
这个题在之前也是讲过，这里再复习一遍吧。
递归版
递归的方法很简单。
具体程序如下：
// 144 二叉树的前序遍历
void preorderTraversal_helper(BiTree root,vector<int>& res){
if(root != NULL){
res.push_back(stoi(root->val));
preorderTraversal_helper(root->left,res);
preorderTraversal_helper(root->right,res);
}
}
vector<int> preorderTraversal(BiTree root){
vector<int> res;
preorderTraversal_helper(root,res);
return res;
}
测试程序如下：
int main(){
//test
//cout<<"test:......"<<endl;
BiTree tree = levelCreate();
vector<int> res = preorderTraversal(tree);
for(auto r : res){
cout<<r<<" ";
}
cout<<endl;
return 0;
}
测试结果为：
1
# 2
3 #
# #
1 2 3
非递归版
具体程序如下：
vector<int> preorderTraversal_(BiTree root){
vector<int> res;
if(root == NULL){
return res;
}
stack<BiTree> s;
BiTree p = root;
s.push(p);
while(!s.empty()){
BiTree node = s.top();
s.pop();
res.push_back(stoi(node->val));
if(node->right){
s.push(node->right);
}
if(node->left){
s.push(node->left);
}
}
return res;
}
测速程序为：
int main(){
//test
//cout<<"test:......"<<endl;
BiTree tree = levelCreate();
vector<int> res = preorderTraversal_(tree);
for(auto r : res){
cout<<r<<" ";
}
cout<<endl;
return 0;
}
测试结果为：
1
# 2
3 #
# #
1 2 3
二叉搜索树中的众数
给定一个有相同值的二叉搜索树（BST），找出 BST 中的所有众数（出现频率最高的元素）。
假定 BST 有如下定义：
结点左子树中所含结点的值小于等于当前结点的值
结点右子树中所含结点的值大于等于当前结点的值
左子树和右子树都是二叉搜索树
图片.png
提示：如果众数超过1个，不需考虑输出顺序
进阶：你可以不使用额外的空间吗？（假设由递归产生的隐式调用栈的开销不被计算在内）
我们知道中序遍历二叉搜索树可以得到一个递增的序列，我们可以使用一个vector保存它，之后在里面寻找众数即可。
具体的程序如下：
// 501 二叉搜索树中的众数
void findMode_helper(BiTree root,vector<int> &res){
if(root != NULL){
findMode_helper(root->left,res);
res.push_back(stoi(root->val));
findMode_helper(root->right,res);
}
}
vector<int> findMode(BiTree root){
vector<int> res;
findMode_helper(root,res);
vector<int> result;
if(res.size() == 1){
result.push_back(res[0]);
}
int cur = 0;
int max = 0;
for(int i = 1;i < res.size();i++){
if(res[i] == res[i-1]){
cur++;
}else{
cur = 0;
}
if(cur == max){
if(i == 1&&cur == 0){
result.push_back(res[0]);
}
result.push_back(res[i]);
}else if(cur > max){
result.clear();
max = cur;
result.push_back(res[i]);
}
}
return result;
}
测试程序如下：
int main(){
//test
//cout<<"test:......"<<endl;
BiTree tree = levelCreate();
vector<int> res = preorderTraversal_(tree);
for(auto r : res){
cout<<r<<" ";
}
cout<<endl;
return 0;
}
测试结果：
1
# 2
2 #
# #
1 2 2
找树左下角的值
给定一个二叉树，在树的最后一行找到最左边的值。
图片.png
注意: 您可以假设树（即给定的根节点）不为 NULL。
这个题我使用的是层序遍历的方式，保留最后一层节点，返回第一个节点即可。
具体程序如下：
// 513 找树左下角的值
int findBottomLeftValue_helper(BiTree root){
if(root == NULL){
return 0;
}
int l = findBottomLeftValue_helper(root->left);
int r = findBottomLeftValue_helper(root->right);
return max(l,r) + 1;
}
int findBottomLeftValue(BiTree root){
int depth = findBottomLeftValue_helper(root);
int level = 1;
queue<BiTree> q;
q.push(root);
while(!q.empty()&&level!=depth){
int n = q.size();
level++;
while(n--){
BiTree node = q.front();
q.pop();
if(node->left){
q.push(node->left);
}
if(node->right){
q.push(node->right);
}
}
}
BiTree node = q.front();
return stoi(node->val);
}
测试程序：
int main(){
//test
//cout<<"test:......"<<endl;
BiTree tree = levelCreate();
cout<<findBottomLeftValue(tree)<<endl;
return 0;
}
测试结果：
2
1 3
# # # #
1
1
2 3
4 # 5 6
# # 7 # # #
# #
7
在每个树行中找最大值
您需要在二叉树的每一行中找到最大的值。
示例：
输入:
1
/ \
3 2
/ \ \
5 3 9
输出: [1, 3, 9]
这个我还是使用层序遍历方式，找每一层最大值保存即可。
具体的程序如下：
// 515 在每个树行中找最大值
vector<int> largestValues(BiTree root){
vector<int> res;
queue<BiTree> q;
if(root == NULL){
return res;
}
q.push(root);
while(!q.empty()){
int n = q.size();
int max_ = INT_MIN;
while(n--){
BiTree node = q.front();
q.pop();
if(stoi(node->val) > max_){
max_ = stoi(node->val);
}
if(node->left){
q.push(node->left);
}
if(node->right){
q.push(node->right);
}
}
res.push_back(max_);
}
return res;
}
测试程序：
int main(){
//test
//cout<<"test:......"<<endl;
BiTree tree = levelCreate();
vector<int> res = largestValues(tree);
for(auto r : res){
cout<<r<<" ";
}
cout<<endl;
return 0;
}
测试结果：
1
3 2
5 3 # 9
# # # # # #
1 3 9
全部代码见 github ，main.cpp 中不带测试程序。
本节内容到此结束，之后将继续更新。
