654. 最大二叉树
方法：模拟
思路
按照题目要求顺序使用递归函数traversal(nums,begin,end)对数组nums二叉树进行模拟。这道题的思路方法与105.从前序遍历和中序遍历中构造二叉树是一致的。
1.确定终止条件，当递归到条件为begin>=end时，返回空指针。
2.通过遍历数组，找出数组中最大值所在的下标以及最大值。
3.使用数组最大值建立根节点
4.使用最大值下标更新begin和end,递归建立根节点的左子树和右子树。
实现
点击查看代码
class Solution {
public:
TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
int begin = 0;
int end = nums.size();
return traversal(nums,begin,end);
}
TreeNode* traversal(vector<int>& nums, int begin,int end){
if(begin == end)return nullptr;
int index = begin;
for(int i = begin;i < end; i++){
if(nums[i] > nums[index]) index = i;
}
TreeNode* root = new TreeNode(nums[index]);
//if(begin == end-1)return root;
int leftbegin = begin;
int leftend = index;
int rightbegin = index+1;
int rightend = end;
root->left = traversal(nums, leftbegin, leftend);
root->right = traversal(nums, rightbegin, rightend);
return root;
}
};
复杂度分析
- 时间复杂度：O(n^2),最坏情况下，即数组是递增或递减情况下，需要递归n层，每层中需要遍历数组寻找最大值，所以时间复杂度为 O(n^2)。
- 空间复杂度：O(n),最坏情况下递归n层，使用的空间为O(n)。
总结
1.构造二叉树算是一种固定的写法，需要熟练掌握。
2.构造二叉树之所以都是前序遍历，是因为节点是单向的，父节点可以找子节点，但子节点无法找父节点。只有先构造父节点，才能构造其左孩子和右孩子。
617. 合并二叉树
方法1：前序遍历（自己的做法，不推荐）
思路
-
终止条件为两个节点都是空节点
-
将节点的三种情况分别处理。
· 节点1为空节点，节点2非空。
· 节点2为空节点，节点1非空。
· 节点1和节点2都是空节点。 -
递归构造左子树和右子树
-
返回根节点
实现
点击查看代码
class Solution {
public:
TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
return traversal(root1,root2);
}
TreeNode* traversal(TreeNode* root1, TreeNode* root2){
if(root1 == nullptr && root2 == nullptr) return nullptr;
TreeNode* root = new TreeNode();
if(root1 != nullptr && root2 != nullptr){
root->val = root1->val + root2->val;
root->left = traversal(root1->left, root2->left);
root->right = traversal(root1->right, root2->right);
}
else if(root1 == nullptr){
root->val = root2->val;
root->left = traversal(nullptr,root2->left);
root->right = traversal(nullptr,root2->right);
}
else if(root2 == nullptr){
root->val = root1->val;
root->left = traversal(nullptr,root1->left);
root->right = traversal(nullptr,root1->right);
}
return root;
}
};
复杂度分析
- 时间复杂度：O(max(m,n))，m,n分别为两棵树的节点数，对每一个节点都要访问。
- 空间复杂度：O(max(m,n)),最坏情况下，是一个链表。
2.前序遍历（推荐）
思路
对前面的做法进行简化，只有当节点1和节点2同时存在时，才需要构造新节点。
实现
点击查看代码
class Solution {
public:
TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
if (t1 == NULL) return t2;
if (t2 == NULL) return t1;
t1->val += t2->val; // 中
t1->left = mergeTrees(t1->left, t2->left); // 左
t1->right = mergeTrees(t1->right, t2->right); // 右
return t1;
}
};
复杂度分析
- 时间复杂度：O(min(m,n)),只有当两个节点都存在时，才需要进行操作
- 空间复杂度：O(min(m,n))
总结
- 这道题的做法其实很简单，本质上是一个遍历二叉树+构造二叉树的题，无论是深度优先遍历还是广度优先遍历都可以进行操作
- 如果按照本来的思路，复杂度较高，通过对终止条件进行优化，可以减小时间复杂度和空间复杂度
700. 二叉搜索树中的搜索
1.递归
思路
- 首先需要知道二叉搜索树与普通二叉树的不同
- 利用二叉搜索树的特性来简化时间复杂度。比较根节点的值与给定值的大小，判断需要搜索左子树还是右子树
root->val ? val。
实现
点击查看代码
class Solution {
public:
TreeNode* searchBST(TreeNode* root, int val) {
return traversal(root, val);
}
TreeNode* traversal(TreeNode* root, int& val) {
if(root == nullptr || root->val == val) return root;
TreeNode* result = nullptr;
if(root->val > val) result = traversal(root->left, val);
if(root->val < val) result = traversal(root->right, val);
return result;
}
};
复杂度分析
- 时间复杂度：O(logn),n为节点的个数，logn为二叉树的层数。因为每一层只需要递归一次，所以时间复杂度为logn。
- 空间复杂度：O(logn)
98. 验证二叉搜索树
思路
中序遍历，不断比较。
实现
点击查看代码
/**
* 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:
bool isValidBST(TreeNode* root) {
return traversal(root);
}
long long val = LONG_MIN;
bool traversal(TreeNode* root){
if(root->left){
if(traversal(root->left) == false) return false;
}
if(root->val > val) {
val = root->val;
}
else {
return false;
}
if(root->right) {
if(traversal(root->right) == false) return false;
}
return true;
}
};
复杂度分析
- 时间复杂度：O(n)
- 空间复杂度：O(n)