day20
654.最大二叉树
题目链接：654. 最大二叉树
解题思路：构造二叉树，采用前序遍历，递归构造
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
// 1.确定递归函数的参数和返回值
TreeNode* construct(vector<int>& nums){
// 定义新节点
TreeNode* node = new TreeNode(0);
// 2.确定终止条件
if ( nums.size() == 1 ){
// return new TreeNode[nums[0]];
node->val = nums[0];
return node;
}
// 3.确定单层递归逻辑
// 找到最大值对应的值和索引
// 中
int maxValue = 0;
int index = 0;
for ( int i = 0; i < nums.size(); i++){
if( nums[i] > maxValue){
maxValue = nums[i];
index = i;
}
}
// 新建根节点
// TreeNode* node = new TreeNode[maxValue];
node->val = maxValue;
// 左
if ( index > 0 ){ //左闭右开
vector<int> vec(nums.begin(),nums.begin()+index);
node->left = construct( vec );
}
// 右
if ( index < (nums.size() - 1)){//左闭右开
vector<int> vec(nums.begin()+index+1,nums.end());
node->right = construct( vec );
}
return node;
}
TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
return construct( nums );
}
};
617.合并二叉树
题目链接：617. 合并二叉树
解题思路：相对于单个二叉树，传入两个树节点，同时操作即可，本题可以以第一个树作为主树最后返回即可，也可以新建一个二叉树
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
// 1.确定返回值和参数
TreeNode* traversal( TreeNode* node1,TreeNode* node2){
// 2.确定终止条件
if ( node1 == NULL ) return node2;
if ( node2 == NULL ) return node1;
// 如果以第一个二叉树为基数
// node1->val += node2->val;
//将下面的root换为node1，最后返回node1
// 定义新的二叉树
TreeNode* root = new TreeNode(0);
// 3.确定单层递归逻辑
root->val = node1->val + node2->val; //中
root->left = traversal( node1->left,node2->left); //左
root->right = traversal( node1->right,node2->right); //右
return root;
}
TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
return traversal( root1,root2);
}
};
// // 定义二叉树结构体
// struct TreeNode{
// int val;
// TreeNode* left;
// TreeNode* right;
// TreeNode(int x):val(x),right(NULL),left(NULL){}
// };
700.二叉搜索树中的搜索
题目链接：700. 二叉搜索树中的搜索
解题思路：使用递归，确定终止条件，注意本题中是有返回值的！！!
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
// 1.确定递归函数返回值和参数
TreeNode* traversal( TreeNode* node, int target){
// TreeNode* result = new TreeNode(0);
// 2.确定终止条件
if( node == NULL || node->val == target ) return node;
// 3.确定单层递归逻辑
// 目标值大于根节点值 右子树遍历
TreeNode* result = NULL;
if (target > node->val){
result = traversal( node-> right ,target);
}
if ( target < node->val){
result = traversal( node->left,target );
}
return result;
}
TreeNode* searchBST(TreeNode* root, int val) {
return traversal( root,val);
}
};
98.验证二叉搜索树
题目链接：98. 验证二叉搜索树
解题思路：递归将二叉搜索树的元素按照中序遍历存入数组，判断数组是否为递增数组，不是则返回false
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
// 中序遍历，搜索二叉树的数组是有序的
vector<int> vec;
void traversal(TreeNode* root){
if( root == NULL ) return;
traversal( root->left ); //左
vec.push_back( root->val );//中
traversal( root->right );//右
}
bool isValidBST(TreeNode* root) {
traversal(root);
for( int i = 1;i < vec.size(); i++){
//判断小于等于，搜索树中不能有相同元素
if(vec[i] <= vec[i-1] ) return false;
}
return true;
}
};