首页 > 代码库 > LeetCode: Recover Binary Search Tree
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?
地址：https://oj.leetcode.com/problems/recover-binary-search-tree/
算法：二叉搜索树中有两个节点被错误的交换了，要求找到这两个节点，并把二者交换回来，要求用常数的空间。首先，使用中序遍历来搜索二叉树，当找到一个树比他的前趋还要小的时候，说明这个点是第一个错误点，即为A，然后接下去找第二个错误点，第二个错误点应该在第一个大于A点值的前面一个节点，记为B，接下去交换A，B节点即可。注意处理B点为最后一个节点时的情况。代码：
/** * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */class Solution {public: void recoverTree(TreeNode *root) { if(!root) return ; stack<TreeNode *> stk; TreeNode *p = root; while(p){ stk.push(p); p = p->left; } TreeNode *pre = NULL; p = NULL; TreeNode *swapped_node1 = NULL; bool is_swapped = false; bool find_node = false; while(!stk.empty()){ pre = p; p = stk.top(); stk.pop(); if(!find_node && pre && pre->val > p->val){ swapped_node1 = pre; find_node = true; } if(find_node && p->val >= swapped_node1->val){ if(pre){ int temp = swapped_node1->val; swapped_node1->val = pre->val; pre->val = temp; is_swapped = true; break; } } if(p->right){ TreeNode *q = p->right; while(q){ stk.push(q); q = q->left; } } } if(!is_swapped){ int temp = swapped_node1->val; swapped_node1->val = p->val; p->val = temp; } return ; }};
LeetCode: Recover Binary Search Tree
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。