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

参考文章均来自代码随想录LeetCode 654 最大二叉树参考文章链接构造二叉树一般使用的都是前序遍历本题也是要切割数组先要找到数组中最大的值和对应的下标 最大的值构造根节点下标用来下一步分割数组最大值所在的下标左区间 构造左子树最大值所在的下标右区间 构造右子树classSolution{public:TreeNode*constructMaximumBinaryTree(vectorintnums){TreeNode*nodenewTreeNode(0);if(nums.size()1){node-valnums[0];returnnode;}// 找到数组中最大的值和对应的下标intmaxValue0;intmaxValueIndex0;for(inti0;inums.size();i){if(nums[i]maxValue){maxValuenums[i];maxValueIndexi;}}node-valmaxValue;// 最大值所在的下标左区间 构造左子树if(maxValueIndex0){vectorintnewVec(nums.begin(),nums.begin()maxValueIndex);node-leftconstructMaximumBinaryTree(newVec);}// 最大值所在的下标右区间 构造右子树if(maxValueIndex(nums.size()-1)){vectorintnewVec(nums.begin()maxValueIndex1,nums.end());node-rightconstructMaximumBinaryTree(newVec);}returnnode;}};LeetCode 617 合并二叉树参考文章链接合并问题 前中后序都可以 前序比较好理解可新建一个二叉树 也可以直接在tree1上构造classSolution{public:TreeNode*mergeTrees(TreeNode*root1,TreeNode*root2){if(root1NULL)returnroot2;if(root2NULL)returnroot1;TreeNode*rootnewTreeNode(0);root-valroot1-valroot2-val;root-leftmergeTrees(root1-left,root2-left);root-rightmergeTrees(root1-right,root2-right);returnroot;}};LeetCode 700 二叉搜索树中的搜索参考文章链接二叉搜索树是一个有序树若它的左子树不空则左子树上所有结点的值均小于它的根结点的值若它的右子树不空则右子树上所有结点的值均大于它的根结点的值它的左、右子树也分别为二叉搜索树这就决定了二叉搜索树递归遍历和迭代遍历和普通二叉树都不一样。可以通过大小比较决定遍历方向classSolution{public:TreeNode*searchBST(TreeNode*root,intval){if(rootNULL||root-valval)returnroot;TreeNode*resultNULL;if(root-valval)resultsearchBST(root-left,val);if(root-valval)resultsearchBST(root-right,val);returnresult;}};LeetCode 98 验证二叉搜索树参考文章链接中序遍历下输出的二叉搜索树节点的数值是有序序列。有了这个特性验证二叉搜索树就相当于变成了判断一个序列是不是递增的了。可以将二叉搜索树转换成数组然后只要比较一下这个数组是否是有序的注意二叉搜索树中不能有重复元素。classSolution{private:vectorintvec;voidtraversal(TreeNode*root){if(rootNULL)return;traversal(root-left);vec.push_back(root-val);// 将二叉搜索树转换为有序数组traversal(root-right);}public:boolisValidBST(TreeNode*root){vec.clear();// 不加这句在leetcode上也可以过但最好加上traversal(root);for(inti1;ivec.size();i){// 注意要小于等于搜索树里不能有相同元素if(vec[i]vec[i-1])returnfalse;}returntrue;}};