[Leetcode] Recover Binary Search Tree

淡淡的烟草味﹌ 2021-12-03 07:25 185阅读 0赞

Two elements of a binary search tree (BST) are swapped by mistake.

Recover the tree without changing its structure.

**Note:**  
A solution using O(*n*) space is pretty straight forward. Could you devise a constant space solution?

中序遍历，对于BST，其中序序列是有序的，所以只要找出中序序列中的逆序对，但是要注意保存中间节点，可以使用全局变量，也可以使用引用。

1 /**
     2  * Definition for binary tree
     3  * struct TreeNode {
     4  *     int val;
     5  *     TreeNode *left;
     6  *     TreeNode *right;
     7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     8  * };
     9  */
    10 class Solution {
    11 public:
    12     void inorder(TreeNode *root, TreeNode *&pos1, TreeNode *&pos2, TreeNode *&pre) {
    13         if (root == NULL) return;
    14         inorder(root->left, pos1, pos2, pre);
    15         if (pre != NULL && pre->val > root->val) {
    16             if (pos1 == NULL) {
    17                 pos1 = pre;
    18                 pos2 = root;
    19             } else {
    20                 pos2 = root;
    21             }
    22         }
    23         pre = root;
    24         inorder(root->right, pos1, pos2, pre);
    25     }
    26     
    27     void recoverTree(TreeNode *root) {
    28         TreeNode *pos1, *pos2, *pre;
    29         pos1 = pos2 = pre = NULL;
    30         inorder(root, pos1, pos2, pre);
    31         swap(pos1->val, pos2->val);
    32     }
    33 };

转载于:https://www.cnblogs.com/easonliu/p/3644294.html

发表评论取消回复

表情：

评论列表（有 0 条评论，185人围观）

还没有评论，来说两句吧...

相关阅读

相关 LeetCode - Medium - 99. Recover Binary Search Tree

Topic Tree Depth-first Search Description [https://leetcode.com/problems/re

拼搏现实的明天。/ 2022年10月06日 11:52/ 0 赞/ 100 阅读

相关 Recover Binary Search Tree--LeetCode

题目：Two elements of a binary search tree (BST) are swapped by mistake.Recover the tree wi

喜欢ヅ旅行/ 2022年08月05日 14:23/ 0 赞/ 174 阅读

相关 Validate Binary Search Tree--LeetCode

题目： Given a binary tree, determine if it is a valid binary search tree (BST). Ass

╰半橙微兮°/ 2022年08月05日 14:18/ 0 赞/ 148 阅读

相关 Unique Binary Search Trees--LeetCode

题目： Given n, how many structurally unique BST's (binary search trees) that store valu

ゞ浴缸里的玫瑰/ 2022年08月05日 14:18/ 0 赞/ 159 阅读

相关 leetcode Binary Search Tree Iterator

题目原题链接：[https://leetcode.com/problems/binary-search-tree-iterator/][https_leetcode.c

素颜马尾好姑娘i/ 2022年08月04日 16:58/ 0 赞/ 174 阅读

相关 LeetCode99—Recover Binary Search Tree

LeetCode99—Recover Binary Search Tree 恢复排序二叉树 -------------------- 原题 > Two elem

谁践踏了优雅/ 2022年07月29日 09:16/ 0 赞/ 127 阅读

相关 [leetcode-二叉查找树的修正]--99. Recover Binary Search Tree

Question 99. Recover Binary Search Tree > Two elements of a binary search tree (BST) ar

绝地灬酷狼/ 2022年07月12日 03:47/ 0 赞/ 172 阅读

相关 [Leetcode][python]Recover Binary Search Tree/恢复二叉搜索树

题目大意一颗二叉查找树中的某两个节点被错误的交换了，需要恢复成原来的正确的二叉查找树。挑战：是要求空间复杂度为常数空间。空间复杂度为O(N)是常规解法。解题思

本是古典何须时尚/ 2022年06月11日 07:10/ 0 赞/ 155 阅读

相关 Leetcode 99. Recover Binary Search Tree O(1)

题目中要求用constant space去结题，那就不能使用中序遍历类似的递归写法，因为这些的空间复杂度平均水平是O(logN)。那么只有使用一种（新的）遍历算法[Morris

红太狼/ 2022年06月09日 06:21/ 0 赞/ 127 阅读

相关 [Leetcode] Recover Binary Search Tree

Two elements of a binary search tree (BST) are swapped by mistake. Recover the tree wit

淡淡的烟草味﹌/ 2021年12月03日 07:25/ 0 赞/ 186 阅读