c/c++开发分享C++实现LeetCode(99.复原二叉搜索树)

[leetcode] 99. recover binary search tree 复原二叉搜索树two elements of a binary search tree (bst) are swap


[leetcode] 99. recover binary search tree 复原二叉搜索

two elements of a binary search tree (bst) are swapped by mistake.

recover the tree without changing its structure.

example 1:

input: [1,3,null,null,2]

   1
/
3

2

output: [3,1,null,null,2]

   3
/
1

2

example 2:

input: [3,1,4,null,null,2]

3
/
1   4
/
2

output: [2,1,4,null,null,3]

  2
/
1   4
/
3

follow up:

  • a solution using o(n) space is pretty straight forward.
  • could you devise a constant space solution?

这道题要求我们复原一个二叉搜索树,说是其中有两个的顺序被调换了,题目要求上说 o(n) 的解法很直观,这种解法需要用到递归,用中序遍历树,并将所有节点存到一个一维向量中,把所有节点值存到另一个一维向量中,然后对存节点值的一维向量排序,在将排好的数组按顺序赋给节点。这种最一般的解法可针对任意个数目的节点错乱的情况,这里先贴上此种解法:

解法一:

  // o(n) space complexity  class solution {  public:      void recovertree(treenode* root) {          vector<treenode*> list;          vector<int> vals;          inorder(root, list, vals);          sort(vals.begin(), vals.end());          for (int i = 0; i < list.size(); ++i) {              list[i]->val = vals[i];          }      }      void inorder(treenode* root, vector<treenode*>& list, vector<int>& vals) {          if (!root) return;          inorder(root->left, list, vals);          list.push_back(root);          vals.push_back(root->val);          inorder(root->right, list, vals);      }  };

然后博主上网搜了许多其他解法,看到另一种是用双指针来代替一维向量的,但是这种方法用到了递归,也不是 o(1) 空间复杂度的解法,这里需要三个指针,first,second 分别表示第一个和第二个错乱位置的节点,pre 指向当前节点的中序遍历的前一个节点。这里用传统的中序遍历递归来做,不过在应该输出节点值的地方,换成了判断 pre 和当前节点值的大小,如果 pre 的大,若 first 为空,则将 first 指向 pre 指的节点,把 second 指向当前节点。这样中序遍历完整个树,若 first 和 second 都存在,则交换它们的节点值即可。这个算法的空间复杂度仍为 o(n),n为树的高度,参见代码如下:

解法二:

  // still o(n) space complexity  class solution {  public:      treenode *pre = null, *first = null, *second = null;      void recovertree(treenode* root) {          inorder(root);          swap(first->val, second->val);      }      void inorder(treenode* root) {          if (!root) return;          inorder(root->left);          if (!pre) pre = root;          else {              if (pre->val > root->val) {                  if (!first) first = pre;                  second = root;              }              pre = root;          }          inorder(root->right);      }  };

我们其实也可以使用迭代的写法,因为中序遍历 binary tree inorder traversal 也可以借助栈来实现,原理还是跟前面的相同,记录前一个结点,并和当前结点相比,如果前一个结点值大,那么更新 first 和 second,最后交换 first 和 second 的结点值即可,参见代码如下:

解法三:

  // always o(n) space complexity  class solution {  public:      void recovertree(treenode* root) {          treenode *pre = null, *first = null, *second = null, *p = root;          stack<treenode*> st;          while (p || !st.empty()) {              while (p) {                  st.push(p);                  p = p->left;              }              p = st.top(); st.pop();              if (pre) {                  if (pre->val > p->val) {                      if (!first) first = pre;                      second = p;                  }              }              pre = p;              p = p->right;          }          swap(first->val, second->val);      }  };

这道题的真正符合要求的解法应该用的 morris 遍历,这是一种非递归且不使用栈,空间复杂度为 o(1) 的遍历方法,可参见博主之前的博客 binary tree inorder traversal,在其基础上做些修改,加入 first, second 和 parent 指针,来比较当前节点值和中序遍历的前一节点值的大小,跟上面递归算法的思路相似,代码如下:

解法四:

  // now o(1) space complexity  class solution {  public:      void recovertree(treenode* root) {          treenode *first = nullptr, *second = nullptr, *cur = root, *pre = nullptr ;          while (cur) {              if (cur->left){                  treenode *p = cur->left;                  while (p->right && p->right != cur) p = p->right;                  if (!p->right) {                      p->right = cur;                      cur = cur->left;                      continue;                  } else {                      p->right = null;                  }                }              if (pre && cur->val < pre->val){                if (!first) first = pre;                second = cur;              }              pre = cur;              cur = cur->right;          }          swap(first->val, second->val);      }  };

到此这篇关于c++实现leetcode(99.复原二叉搜索树)的文章就介绍到这了,更多相关c++实现复原二叉搜索树内容请搜索<猴子技术宅>以前的文章或继续浏览下面的相关文章希望大家以后多多支持<猴子技术宅>!

需要了解更多c/c++开发分享C++实现LeetCode(99.复原二叉搜索树),都可以关注C/C++技术分享栏目—猴子技术宅(www.ssfiction.com)

本文来自网络收集,不代表猴子技术宅立场,如涉及侵权请点击右边联系管理员删除。

如若转载,请注明出处:https://www.ssfiction.com/c-cyuyankaifa/674052.html

发表评论

邮箱地址不会被公开。 必填项已用*标注