代码随想录算法训练营第十七天| LeetCode 654 最大二叉树、LeetCode 617 合并二叉树、LeetCode 700 二叉搜索树中的搜索、LeetCode 98 验证二叉搜索树

参考文章均来自代码随想录

LeetCode 654 最大二叉树

参考文章链接

构造二叉树一般使用的都是前序遍历
本题也是要切割数组

先要找到数组中最大的值和对应的下标， 最大的值构造根节点，下标用来下一步分割数组

最大值所在的下标左区间 构造左子树

最大值所在的下标右区间 构造右子树

classSolution{public:TreeNode*constructMaximumBinaryTree(vector<int>&nums){TreeNode*node=newTreeNode(0);if(nums.size()==1){node->val=nums[0];returnnode;}// 找到数组中最大的值和对应的下标intmaxValue=0;intmaxValueIndex=0;for(inti=0;i<nums.size();i++){if(nums[i]>maxValue){maxValue=nums[i];maxValueIndex=i;}}node->val=maxValue;// 最大值所在的下标左区间 构造左子树if(maxValueIndex>0){vector<int>newVec(nums.begin(),nums.begin()+maxValueIndex);node->left=constructMaximumBinaryTree(newVec);}// 最大值所在的下标右区间 构造右子树if(maxValueIndex<(nums.size()-1)){vector<int>newVec(nums.begin()+maxValueIndex+1,nums.end());node->right=constructMaximumBinaryTree(newVec);}returnnode;}};

LeetCode 617 合并二叉树

参考文章链接

合并问题 前中后序都可以 前序比较好理解
可新建一个二叉树 也可以直接在tree1上构造

classSolution{public:TreeNode*mergeTrees(TreeNode*root1,TreeNode*root2){if(root1==NULL)returnroot2;if(root2==NULL)returnroot1;TreeNode*root=newTreeNode(0);root->val=root1->val+root2->val;root->left=mergeTrees(root1->left,root2->left);root->right=mergeTrees(root1->right,root2->right);returnroot;}};

LeetCode 700 二叉搜索树中的搜索

参考文章链接

二叉搜索树是一个有序树：

若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
它的左、右子树也分别为二叉搜索树

这就决定了，二叉搜索树，递归遍历和迭代遍历和普通二叉树都不一样。可以通过大小比较决定遍历方向

classSolution{public:TreeNode*searchBST(TreeNode*root,intval){if(root==NULL||root->val==val)returnroot;TreeNode*result=NULL;if(root->val>val)result=searchBST(root->left,val);if(root->val<val)result=searchBST(root->right,val);returnresult;}};

LeetCode 98 验证二叉搜索树

参考文章链接

中序遍历下，输出的二叉搜索树节点的数值是有序序列。

有了这个特性，验证二叉搜索树，就相当于变成了判断一个序列是不是递增的了。

可以将二叉搜索树转换成数组
然后只要比较一下，这个数组是否是有序的，注意二叉搜索树中不能有重复元素。

classSolution{private:vector<int>vec;voidtraversal(TreeNode*root){if(root==NULL)return;traversal(root->left);vec.push_back(root->val);// 将二叉搜索树转换为有序数组traversal(root->right);}public:boolisValidBST(TreeNode*root){vec.clear();// 不加这句在leetcode上也可以过，但最好加上traversal(root);for(inti=1;i<vec.size();i++){// 注意要小于等于，搜索树里不能有相同元素if(vec[i]<=vec[i-1])returnfalse;}returntrue;}};