目录
一、(leetcode 654)最大二叉树
二、(leetcode 617)合并二叉树
三、(leetcode 700)二叉搜索树中的搜索
四、(leetcode 98)验证二叉搜索树
一、(leetcode 654)最大二叉树
力扣题目地址
状态:AC。
和昨天的中序+后/前序遍历序列构建二叉树思路类似,每次递归寻找数组中的最大值,根据最大值的索引来切分左右子序列进行递归生成,可以用索引下标来避免重复生成vector带来的开销
class Solution {
public:TreeNode* traversal(vector<int>& nums, int begin, int end){if(begin == end) { return nullptr; }int max_num = INT_MIN, max_index = begin;// 确定最大值的索引for(int i = begin; i < end; ++i){if(max_num < nums[i]){max_num = nums[i];max_index = i;}}TreeNode* node = new TreeNode(max_num);// 进行左右子数组划分int left_left = begin, left_right = max_index;int right_left = max_index + 1, right_right = end;node->left = traversal(nums, left_left, left_right);node->right = traversal(nums, right_left, right_right);return node;}TreeNode* constructMaximumBinaryTree(vector<int>& nums) {return traversal(nums, 0, nums.size());}
};
二、(leetcode 617)合并二叉树
力扣题目链接
状态:AC。
使用的方法可以AC但是不够简洁,留待后续改进
class Solution {
public:TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {//进行前序遍历,如果两棵树都为空则返回空节点if(root1 == nullptr && root2 == nullptr){return nullptr;}TreeNode* node = new TreeNode(0);if(root1 != nullptr && root2 != nullptr){node->val = root1->val + root2->val;node->left = mergeTrees(root1->left, root2->left);node->right = mergeTrees(root1->right, root2->right);}else if(root1){node->val = root1->val;node->left = mergeTrees(root1->left, nullptr);node->right = mergeTrees(root1->right, nullptr);}else{node->val = root2->val;node->left = mergeTrees(nullptr, root2->left);node->right = mergeTrees(nullptr, root2->right);}return node; }
};
三、(leetcode 700)二叉搜索树中的搜索
力扣题目地址
状态:AC。
简单的前序遍历比较
class Solution {
public:TreeNode* searchBST(TreeNode* root, int val) {if(root == nullptr) return nullptr;//前序遍历if(root->val == val){return root;}else if(root->val < val){return searchBST(root->right, val);}else{return searchBST(root->left, val);}return nullptr;}
};
四、(leetcode 98)验证二叉搜索树
力扣题目链接
状态:思路错误,不能简单地比较根节点和左右子节点的大小。
这道题可以通过中序遍历的顺序判断值是不是递增来判断,注意除了上面的那个思路问题,在实现时用于比较的值maxVal需要使用long long来初始化,以防测试用例中有INT_MIN。
class Solution {
public:long long maxVal = LONG_MIN;bool isValidBST(TreeNode* root) {if(root == nullptr) return true;bool left = isValidBST(root->left);//中序遍历查看是否符合递增if(root->val > maxVal){maxVal = root->val;}else{return false;}bool right = isValidBST(root->right);return left && right;}
};