[leetcode653]两数之和Ⅳ-输入bst

原题 给定一个bst和一个整数k 问是否存在两个数字之和等于k 表面上是个easy题 实际上有点困难

dfs

直接使用dfs 类似leetcode第一题做法 缺点是未使用到bst中序有序这一特点

class Solution
{
public:
  set<int> st;
  bool findTarget(TreeNode *root, int k)
  {
    if(root==nullptr) return false;
    if(st.count(k-root->val)) return true;//找到了
    st.insert(root->val);
    //递归寻找左右子树
    return findTarget(root->left,k)findTarget(root->right,k);
  }
};

dfs+中序遍历+双指针

中序遍历得到一个有序数列 同时头尾两个双指针判断是否合法

class Solution
{
public:
  vector<int> v;
  void inorderTraverval(TreeNode *root)
  {
    if (root == nullptr)
    {
      return;
    }
    inorderTraverval(root->left);
    v.emplace_back(root->val);
    inorderTraverval(root->right);
  }
  bool findTarget(TreeNode *root, int k)
  {
    //中序遍历得到有序序列
    inorderTraverval(root);
    //定义双指针
    int left=0,right=v.size()-1;
    while(left<right){
      if(v[left]+v[right]==k){
        return true;
      }
      if(v[left]+v[right]<k){
        left++;
      }else{
        right--;
      }
    }
    return false;
  }
};

dfs+中序遍历+双指针

去除空间占用（但是写起来麻烦了不少 使用栈的思想来寻找上一个节点/下一个节点
先将树的左侧和右侧分别放入两个栈中 这样栈顶元素分别是最大值和最小值 之后和上一个做法差不多

class Solution
{
public:
  TreeNode *getLeft(stack<TreeNode *> &st)
  {
    //寻找下一个
    TreeNode *p = st.top(); //栈顶元素
    st.pop();
    // p节点的右节点是p节点的下一个节点
    TreeNode *t = p->right;
    while (t != nullptr)
    {
      st.push(t);
      t = t->left;
    }
    return p;
  }
  TreeNode *getRight(stack<TreeNode *> &st)
  {
    //寻找前一个
    TreeNode *p = st.top(); //栈顶元素
    st.pop();
    // p节点的右节点是p节点的下一个节点
    TreeNode *t = p->left;
    while (t != nullptr)
    {
      st.push(t);
      t = t->right;
    }
    return p;
  }
  bool findTarget(TreeNode *root, int k)
  {
    TreeNode *l = root, *r = root;
    stack<TreeNode *> lst, rst; //两个栈
    lst.push(l);
    while (l->left != nullptr)
    {
      lst.push(l->left);
      l = l->left;
    }
    rst.push(r);
    while (r->right != nullptr)
    {
      rst.push(r->right);
      r = r->right;
    }
    //入栈完毕
    while (l != r)
    {
      if (l->val + r->val == k)
        return true;
      if (l->val + r->val < k)
      {
        l = getLeft(lst);
      }
      else
      {
        r = getRight(rst);
      }
    }
    return false;
  }
};