程序员人生 网站导航

leetcode笔记:Recover Binary Search Tree

栏目:php教程时间:2016-03-31 08:31:55

1. 题目描写

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?

2. 题目分析

题目的大意是,在2叉排序树中有两个节点被交换了,要求把树恢复成2叉排序树。

1个最简单的办法是,中序遍历2叉树生成序列,然后对序列中排序毛病的进行调剂。最后再进行1次赋值操作。这类方法的空间复杂度为O(n)。

但是,题目中要求空间复杂度为常数,所以需要换1种方法。

递归中序遍历2叉树,设置1个prev指针,记录当前节点中序遍用时的前节点,如果当前节点大于prev节点的值,说明需要调剂次序。

3. 示例代码

/** * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: TreeNode *p,*q; TreeNode *prev; void recoverTree(TreeNode *root) { p=q=prev=NULL; inorder(root); swap(p->val,q->val); } void inorder(TreeNode *root) { if(root->left)inorder(root->left); if(prev!=NULL&&(prev->val>root->val)) { if(p==NULL)p=prev; q=root; } prev=root; if(root->right)inorder(root->right); } };

4. 小结

有1个技能是,若遍历全部序列进程中只出现了1次次序毛病,说明就是这两个相邻节点需要被交换。如果出现了两次次序毛病,那就需要交换这两个节点。

------分隔线----------------------------
------分隔线----------------------------

最新技术推荐