当前位置：首页 > news >正文

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

news 2024/11/2 5:28:54

day17

1. 654最大二叉树

类似106题思路

  class Solution {
public:TreeNode* Max (vector<int>& num) {if (num.size() == 0) return NULL;// 数组中最大的一个元素，就是当前的根节点int max=num[0];int j=0;for(int i=1;i<num.size();i++){if(max<num[i]){max=num[i];j=i;}}TreeNode* root = new TreeNode(max);// 叶子节点if (num.size() == 1) return root;// 切割数组，左闭右开// [0, j)vector<int> leftnum(num.begin(), num.begin() + j);// [j+1, end)vector<int> rightnum(num.begin() + j +1, num.end());root->left = Max(leftnum);root->right = Max(rightnum);return root;}TreeNode* constructMaximumBinaryTree(vector<int>& nums) {return Max(nums);}
};

2. 617合并二叉树

确定递归函数的参数和返回值：

首先要合入两个二叉树，那么参数至少是要传入两个二叉树的根节点，返回值就是合并之后二叉树的根节点。

代码如下：

TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {

确定终止条件：

因为是传入了两个树，那么就有两个树遍历的节点t1 和 t2，如果t1 == NULL 了，两个树合并就应该是 t2 了（如果t2也为NULL也无所谓，合并之后就是NULL）。

反过来如果t2 == NULL，那么两个数合并就是t1（如果t1也为NULL也无所谓，合并之后就是NULL）。

代码如下：

if (t1 == NULL) return t2; // 如果t1为空，合并之后就应该是t2
if (t2 == NULL) return t1; // 如果t2为空，合并之后就应该是t1

确定单层递归的逻辑：

单层递归的逻辑就比较好写了，这里我们重复利用一下t1这个树，t1就是合并之后树的根节点（就是修改了原来树的结构）。

那么单层递归中，就要把两棵树的元素加到一起。

t1->val += t2->val;

接下来t1 的左子树是：合并 t1左子树 t2左子树之后的左子树。

t1 的右子树：是合并 t1右子树 t2右子树之后的右子树。

最终t1就是合并之后的根节点。

代码如下：

t1->left = mergeTrees(t1->left, t2->left);
t1->right = mergeTrees(t1->right, t2->right);
return t1;

整体代码如下：

class Solution {
public:TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {if (t1 == NULL) return t2; // 如果t1为空，合并之后就应该是t2if (t2 == NULL) return t1; // 如果t2为空，合并之后就应该是t1// 修改了t1的数值和结构t1->val += t2->val;                             // 中t1->left = mergeTrees(t1->left, t2->left);      // 左t1->right = mergeTrees(t1->right, t2->right);   // 右return t1;}
};

3. 700二叉搜索树中的搜索

确定递归函数的参数和返回值：
递归函数的参数是 TreeNode* root 和 int val，表示要查找的二叉树的当前节点和目标值。返回值是 TreeNode* 类型，用于返回找到的目标节点的指针，如果未找到则返回 NULL。
确定终止条件：
终止条件是当当前节点 root 为 NULL 时，说明已经到达叶节点的末端且未找到目标值，返回 NULL。
另外，当 root->val == val 时，说明找到了目标节点，返回当前节点的指针 root。
确定单层递归的逻辑：
如果当前节点的值不等于目标值，则递归地在左子树和右子树中继续查找：

首先在左子树中调用 searchBST(root->left, val)，返回左子树的结果 l。

继续在右子树中查找 searchBST(root->right, val)，返回右子树的结果 r。

如果左子树找到了目标节点，则返回左子树的结果 l。如果右子树找到了目标节点，返回右子树的结果 r；如果左右子树都未找到，则返回 NULL。

class Solution {
public:TreeNode* searchBST(TreeNode* root, int val) {if(root==NULL) return NULL;if(root->val==val){return root;}TreeNode* l= searchBST(root->left,val);TreeNode* r= searchBST(root->right,val);if(l){return l;}else if(r){return r;}else{return NULL;}}
};

4. 98验证二叉搜索树

中序遍历结果即是有效的二叉搜索树的结果，通过中序遍历得到数组结果，只需判断数组元素是否递增即可。

class Solution {
public:void traversal(TreeNode* cur, vector<int>& vec) {if (cur == NULL) return;traversal(cur->left, vec);  // 左vec.push_back(cur->val);    // 中traversal(cur->right, vec); // 右}bool isValidBST(TreeNode* root) {vector<int> vec;traversal(root, vec);for(int i=0;i<vec.size()-1;i++){if(vec[i+1]<=vec[i]){return false;}}return true;}
};

查看全文

http://www.mrgr.cn/news/63819.html