首页 > 代码库 > [LeetCode] Recover Binary Search Tree
[LeetCode] Recover Binary Search Tree
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?
思路：中序递归的思路。用pre记录前一个节点，找出违反二叉搜索树规则的节点。中序遍历序列中，第一次违反二叉搜索树规则的节点的前一个节点是要修改的节点。第二次违反二叉搜索树规则的节点本身是要修改的节点
时间复杂度O(n),空间复杂度O(1)
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 TreeNode *pre = NULL;13 TreeNode *mistake_node1 = NULL;14 TreeNode *mistake_node2 = NULL;15 16 void InorderTraversal(TreeNode *root) {17 if (root != NULL) {18 InorderTraversal(root->left);19 20 if (pre != NULL && root->val < pre->val) {21 if (!mistake_node1) {22 mistake_node1 = pre;23 mistake_node2 = root;24 } else {25 mistake_node2 = root;26 }27 }28 pre = root;29 InorderTraversal(root->right);30 }31 }32 void recoverTree(TreeNode *root) {33 InorderTraversal(root);34 if (mistake_node1 && mistake_node2)35 swap(mistake_node1->val, mistake_node2->val);36 }37 };
[LeetCode] Recover Binary Search Tree
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。