本文主要是介绍代码随想录算法训练营第二十天| ● 654.最大二叉树 ● 617.合并二叉树 ● 700.二叉搜索树中的搜索 ● 98.验证二叉搜索树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
层序遍历、回溯·、由两种遍历序列逆推二叉树
654.最大二叉树
思路：
理解题意，找到数组最大值，其左元素为左子树，其右元素为右子树
特殊情况：
代码实现
class Solution {
public:int findMax(const vector<int>& nums, int left, int right){if(left > right) -1;int maxNum = nums[left]; int maxIndex = left;for(int i = left; i <= right; i++){if(nums[i] > maxNum) {maxIndex = i;maxNum = nums[i];}}return maxIndex;}TreeNode* BinaryTree(const vector<int>& nums, int left, int right){if(left > right) return nullptr;int rootIndex = findMax(nums, left, right);if(rootIndex < 0) return nullptr;TreeNode* node = new TreeNode(nums[rootIndex]);node->left = BinaryTree(nums, left, rootIndex-1);node->right = BinaryTree(nums, rootIndex+1, right);return node;}TreeNode* constructMaximumBinaryTree(vector<int>& nums) {if(nums.empty()) return nullptr;return BinaryTree(nums, 0, nums.size()-1);}
};
617.合并二叉树
思路：
分三种情况合并：
当前节点的左右节点均为空，则合并结果为空；
左右节点存在一个为空，则合并结果为另一个节点；
左右节点均步为空，则创建一个新节点，其值为左右节点之和
特殊情况：
class Solution {
public:TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {if(root1 == nullptr && root2 == nullptr) return nullptr;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;}
};
700.二叉搜索树中的搜索
思想：二叉搜索树的节点值比左节点大，比右节点小
所以当前节点值比目标值小，则向右子树遍历；比目标值大，则向左子树遍历；
代码实现
class Solution {
public:TreeNode* searchBST(TreeNode* root, int val) {if(root == nullptr) return nullptr;if(root->val == val) return root;TreeNode* node;if(root->val > val){node = searchBST(root->left, val);}else{node = searchBST(root->right,val);}return node;}
};
98.验证二叉搜索树
思想：二叉搜索树的中序序列时严格递增序列
步骤：
分几步：
● 第一步：中序遍历得到中序序列
● 第二步：遍历中序序列，若为递增则不是二叉搜索树
代码实现
class Solution {
public:void inOrder(TreeNode* root, vector<int> &InorderVals){if(root == nullptr) return;inOrder(root->left, InorderVals);InorderVals.push_back(root->val);inOrder(root->right, InorderVals);}bool isValidBST(TreeNode* root) {if(root == nullptr) return true;vector<int> InorderVals;inOrder(root, InorderVals);for(int i = 0; i < InorderVals.size()-1; i++){if(InorderVals[i] >= InorderVals[i+1]) return false;}return true;}
};
这篇关于代码随想录算法训练营第二十天| ● 654.最大二叉树 ● 617.合并二叉树 ● 700.二叉搜索树中的搜索 ● 98.验证二叉搜索树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
