十五、合并二叉树
题目
给你两棵二叉树: root1
和 root2
。
想象一下,当你将其中一棵覆盖到另一棵之上时,两棵树上的一些节点将会重叠(而另一些不会)。你需要将这两棵树合并成一棵新二叉树。合并的规则是:如果两个节点重叠,那么将这两个节点的值相加作为合并后节点的新值;否则,不为 null 的节点将直接作为新二叉树的节点。
返回合并后的二叉树。
注意: 合并过程必须从两个树的根节点开始。
- 同时遍历两棵树
题解
class Solution {
public:
TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
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;
}
};
十六、二叉搜索树中的搜索
二叉搜索树是一个有序树
- 若左子树不为空,则左子树上所有结点的值均小于它的根结点的值;
- 若右子树不空,则右子树上所有结点均大于它的根结点的值
- 它的左右子树也分别为二叉树
题目
给定二叉搜索树(BST)的根节点 root
和一个整数值 val
。
你需要在 BST 中找到节点值等于 val
的节点。 返回以该节点为根的子树。 如果节点不存在,则返回 null
。
题解
class Solution {
public:
TreeNode* searchBST(TreeNode* root, int val) {
if(root == nullptr || root->val == val) return root;
if(root->val > val) return searchBST(root->left, val);
if(root->val < val) return searchBST(root->right, val);
return nullptr;
}
};
十七、验证二叉树
知识点
- 中序遍历下,输出的二叉树是递增的(左中右)
题目
给你一个二叉树的根节点 root
,判断其是否是一个有效的二叉搜索树。
有效 二叉搜索树定义如下:
- 节点的左子树只包含 小于 当前节点的数。
- 节点的右子树只包含 大于 当前节点的数。
- 所有左子树和右子树自身必须也是二叉搜索树。
题解
class Solution {
public:
long long maxVal = LONG_MIN;
bool isValidBST(TreeNode* root) {
if(root == nullptr) return true;
bool left = isValidBST(root->left);
if(maxVal < root->val) maxVal = root->val;
else return false;
bool right = isValidBST(root->right);
return right && left;
}
};
十八、二叉搜索树的最小绝对差
知识点
- 二叉数组是有序的,那么也就是说,所有关于在二叉树上求差值或者最值,都可以当作一个有序数组求差值或者最值。
题目
给你一个二叉搜索树的根节点 root
,返回 树中任意两不同节点值之间的最小差值 。
差值是一个正数,其数值等于两值之差的绝对值。
530. 二叉搜索树的最小绝对差 - 力扣(LeetCode)
题解
class Solution {
public:
vector<int> vec;
void traverse(TreeNode*root){
if(root == nullptr) return;
traverse(root->left);
vec.push_back(root->val);
traverse(root->right);
}
int getMinimumDifference(TreeNode* root) {
vec.clear();
traverse(root);
int result = INT_MAX;
if(vec.size() < 2) return root->val;
for(int i = 1; i < vec.size(); i++){
result = min(result, vec[i] - vec[i - 1]);
}
return result;
}
};
最近又是三八节,女神节,呜呜尝试找借口说自己不想刷算法,加油鸭!坚持坚持~