力扣数据结构14天学习计划day14

力扣98

力扣98—验证二叉搜索树

题意

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

有效 二叉搜索树定义如下：

• 节点的左子树只包含 小于 当前节点的数。
• 节点的右子树只包含 大于 当前节点的数。
• 所有左子树和右子树自身必须也是二叉搜索树。

解法1—中序遍历

二叉搜索树的中序遍历是递增的，在中序遍历的过程中，我们只需要判断上一个元素与当前元素的大小关系，如果上一个元素≥当前元素，则证明这不是一颗二叉搜索树，只需返回false即可。最后遍历完整颗二叉树后，返回true即可。

class Solution 
{
public:bool isValidBST(TreeNode* root) {if(nullptr==root)return true;if(nullptr==root->left&&nullptr==root->right)return true;long pre = LLONG_MIN;stack st;while(!st.empty()||root){while(root){st.push(root);root=root->left;}root=st.top();st.pop();if(pre>=root->val){return false;}pre=root->val;root=root->right;}return true;}};

 力扣653—两数之和Ⅳ-输入 BST

力扣653

题意

给定一个二叉搜索树 root 和一个目标结果 k，如果 BST 中存在两个元素且它们的和等于给定的目标结果，则返回 true。 

解法1—哈希表

class Solution 
{
public:bool findTarget(TreeNode* root, int k) {if(nullptr==root)return false;unordered_setuset;stackst;while(!st.empty()||root){while(root){st.push(root);root=root->left;}root=st.top();st.pop();if(uset.count(k-root->val))return true;uset.insert(root->val);//if(uset.count(k-root->val)&&(k-root->val)!=root->val)//   return true;root=root->right;}return false;}
};

 解法2—中序遍历+双指针

二叉搜索数的中序遍历会得到一个递增序列，然后利用双指针求出这个递增序列是否存在两个数相加得到目标值。

class Solution 
{
private:vectorvec;
public:void in_order(TreeNode* root){if(nullptr==root)return;in_order(root->left);vec.push_back(root->val);in_order(root->right);}bool findTarget(TreeNode* root, int k) {if(nullptr==root)return false;in_order(root);//双指针int i=0,j=vec.size()-1;while(ik)j--;elsereturn true;}return false;/*unordered_setuset;stackst;while(!st.empty()||root){while(root){st.push(root);root=root->left;}root=st.top();st.pop();if(uset.count(k-root->val))return true;uset.insert(root->val);//if(uset.count(k-root->val)&&(k-root->val)!=root->val)//  return true;root=root->right;}return false;*/}
};

力扣235—二叉搜索树的最近公共祖先

力扣235

题意

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

例如，给定如下二叉搜索树:  root = [6,2,8,0,4,7,9,null,null,3,5]

解法1—非递归（适用于二叉搜索树）

我们从根节点开始遍历，具体的算法流程：

1. 如果两个节点值都小于根节点，说明他们都在根节点的左子树上，我们往左子树上找
2. 如果两个节点值都大于根节点，说明他们都在根节点的右子树上，我们往右子树上找
3. 如果一个节点值大于根节点，一个节点值小于根节点，说明他们他们一个在根节点的左子树上一个在根节点的右子树上，那么根节点就是他们的最近公共祖先节点。

class Solution 
{
public:TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {//判断p和q的位置int p_val=p->val,q_val=q->val,root_val=root->val;//如果root的值与p、q的值之差，相乘结果大于0，说明p和q都在root的同一侧while((root_val-p_val)*(root_val-q_val)>0){// 如果root值比他们大，说明p、q都在root左侧，否则在root右侧root=root_val>p_val?root->left:root->right;root_val=root->val;}//如果root的值与p、q的值之差，相乘结果小于0，说明p和q都在root的两侧，root就是他们最近的祖先节点//如果相乘结果为0，说明p和q至少有一个就是rootreturn root;}
};

 解法2—递归（适用于二叉搜索树）

class Solution 
{
public:TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {//递归解决if((root->val-p->val)*(root->val-q->val)<=0){//如果相乘结果小于等于0，说明p、q在root两侧//或者 p、q有一个就是rootreturn root;}//否则，p、q同时在root的一侧root=root->val>p->val?root->left:root->right;return lowestCommonAncestor(root,p,q);/*非递归解决//判断p和q的位置int p_val=p->val,q_val=q->val,root_val=root->val;//如果root的值与p、q的值之差，相乘结果大于0，说明p和q都在root的同一侧while((root_val-p_val)*(root_val-q_val)>0){// 如果root值比他们大，说明p、q都在root左侧，否则在root右侧root=root_val>p_val?root->left:root->right;root_val=root->val;}//如果root的值与p、q的值之差，相乘结果小于0，说明p和q都在root的两侧，root就是他们最近的祖先节点//如果相乘结果为0，说明p和q至少有一个就是rootreturn root;*/}
};

解法3—二叉树和二叉搜索树都适合

class Solution 
{
public://函数作用是，在以 root 为根的这棵树里面，如果能找到p就返回p出去，能找到q，就返回q出去//如果p和q都可以找到的话，就返回root TreeNode* find_p_or_q(TreeNode* root,TreeNode* p,TreeNode* q){if(root==nullptr||root==p||root==q)return root;TreeNode* left=find_p_or_q(root->left,p,q);TreeNode* right=find_p_or_q(root->right,p,q);if(nullptr!=left&&nullptr!=right){//如果在root为根的这棵树里面，左右子树中都能够找到p和q//说明，p、q分布在这颗树的左右两侧，root就是他们的公共祖先return root;}else if(nullptr==left&&nullptr==right){//在左右子树中都没有找到p和q，说明这棵树中没有他们的公共祖先return nullptr;}else if(nullptr==left){//如果在左子树中没找到p或者q//直接返回右子树结果即可return right;}else if(nullptr==right){//同上return left;}return nullptr;}TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {//二叉树和二叉搜索树都适合的解法return find_p_or_q(root,p,q);//递归解决/*if((root->val-p->val)*(root->val-q->val)<=0){//如果相乘结果小于等于0，说明p、q在root两侧//或者 p、q有一个就是rootreturn root;}//否则，p、q同时在root的一侧root=root->val>p->val?root->left:root->right;return lowestCommonAncestor(root,p,q);*//*非递归解决//判断p和q的位置int p_val=p->val,q_val=q->val,root_val=root->val;//如果root的值与p、q的值之差，相乘结果大于0，说明p和q都在root的同一侧while((root_val-p_val)*(root_val-q_val)>0){// 如果root值比他们大，说明p、q都在root左侧，否则在root右侧root=root_val>p_val?root->left:root->right;root_val=root->val;}//如果root的值与p、q的值之差，相乘结果小于0，说明p和q都在root的两侧，root就是他们最近的祖先节点//如果相乘结果为0，说明p和q至少有一个就是rootreturn root;*/}
};

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！