二叉树|654.最大二叉树、617.合并二叉树、700.二叉搜索树中的搜索、98.验证二叉搜索树
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:
TreeNode* dfs(vector<int>& nums, int start, int end) {
if(start >= end) return nullptr;
int split = start;
int max = INT_MIN;
for(int i = start; i < end; i++) { // 这里范围缩小到[start, end)
if(nums[i] > max) {
max = nums[i];
split = i;
}
}
TreeNode* root = new TreeNode(max);
int leftStart = start;
int leftEnd = split;
int rightStart = split + 1;
int rightEnd = end;
root->left = dfs(nums, leftStart, leftEnd);
root->right = dfs(nums, rightStart, rightEnd);
return root;
}
TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
if(nums.size() == 0) return nullptr;
return dfs(nums, 0, nums.size());
}
这里和构造二叉树不同点在于:
寻找根节点(最大值要在[start,end)范围内找),构造二叉树是确定二叉树根节点的数值且数值不重复,所以在整个数组内寻找根节点下标;而该题需要寻找分割数组内的最大值坐标。
参考详解
617.合并二叉树
自己审题思路
同步遍历
看完代码随想录题解后的收获
遍历两个树递归返回值问题
代码(修改root1结构):
class Solution {
public:
TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
if(root1 == nullptr) return root2;
if(root2 == nullptr) return root1;
root1->val += root2->val;
root1->left = mergeTrees(root1->left, root2->left);
root1->right = mergeTrees(root1->right, root2->right);
return root1;
}
};
因为是传入了两个树,那么就有两个树遍历的节点
root1
和root2
,如果root1 == NULL
了,两个树合并就应该是root2
了(如果root2
也为NULL
也无所谓,合并之后就是NULL
)。
反过来如果root2 == NULL
,那么两个数合并就是root1
(如果root1
也为NULL也无所谓,合并之后就是NULL
)。
代码(构建一个新树)
class Solution {
public:
TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
if (t1 == NULL) return t2;
if (t2 == NULL) return t1;
// 重新定义新的节点,不修改原有两个树的结构
TreeNode* root = new TreeNode(0);
root->val = t1->val + t2->val;
root->left = mergeTrees(t1->left, t2->left);
root->right = mergeTrees(t1->right, t2->right);
return root;
}
};
参考详解
700.二叉搜索树中的搜索
自己审题思路
利用二叉搜索树特性来遍历二叉树
看完代码随想录题解后的收获
了解二叉搜索树特性
代码:
class Solution {
public:
TreeNode* searchBST(TreeNode* root, int val) {
if(root == nullptr) return nullptr;
if(root->val == val) return root;
TreeNode* ans = nullptr;
if(val < root->val) ans = searchBST(root->left, val);
if(val > root->val) ans = searchBST(root->right, val);
return ans;
}
};
参考详解
98.验证二叉搜索树
自己审题思路
利用二叉搜索树特性来遍历
看完代码随想录题解后的收获
二叉搜索树使用中序遍历
代码:
class Solution {
public:
long long maxValue = LONG_MIN;
bool isValidBST(TreeNode* root) {
if(root == nullptr) return true;
bool isLeft = isValidBST(root->left);
if(maxValue < root->val) maxValue = root->val;
else return false;
bool isRight =isValidBST(root->right);
return isLeft && isRight;
}
};
代码(前一个节点比较后一个节点(中序)):
class Solution {
public:
TreeNode* pre = nullptr;
bool isValidBST(TreeNode* root) {
if(root == nullptr) return true;
bool isLeft = isValidBST(root->left);
if(pre != nullptr && pre->val >= root->val) return false;
pre = root;
bool isRight =isValidBST(root->right);
return isLeft && isRight;
}
};
代码(迭代):
class Solution {
public:
bool isValidBST(TreeNode* root) {
stack<TreeNode*> st;
if(root == nullptr) return true;
TreeNode* cur = root;
TreeNode* pre = nullptr;
while(!st.empty() || cur != nullptr) {
while(cur != nullptr) {
st.push(cur);
cur = cur->left;
}
cur = st.top(); st.pop();
if(pre != nullptr && pre->val >= cur->val) return false;
pre = cur;
cur = cur->right;
}
return true;
}
};
代码(将二叉树转化为有序数组):
class Solution {
private:
vector<int> vec;
void traversal(TreeNode* root) {
if (root == NULL) return;
traversal(root->left);
vec.push_back(root->val); // 将二叉搜索树转换为有序数组
traversal(root->right);
}
public:
bool isValidBST(TreeNode* root) {
vec.clear(); // 不加这句在leetcode上也可以过,但最好加上
traversal(root);
for (int i = 1; i < vec.size(); i++) {
// 注意要小于等于,搜索树里不能有相同元素
if (vec[i] <= vec[i - 1]) return false;
}
return true;
}
};