首页 > 代码库 > java swing实现小球沿正弦曲线运动的代码
java swing实现小球沿正弦曲线运动的代码
问题:
给定的二叉查找树中,有两个节点不小心被调换了位置,现在需要将其修正,不改变树的结构。
分析:
二叉排序树的中序遍历是有序的,所以这个问题又是建立在中序遍历模板上的问题,所以我们可以对其进行中序遍历,并用一个pre指针指向当前遍历结果中的最后一个结点,即下次遍历前的前一个结点。然后就可以通过将当前结点与pre结点进行比较,来判断是否有序了。若乱序,就将这两个结点都放入到预先定义的容器中。
错误的形式就这两种,我们看到,在乱序容器中,最多就存了四个元素,所以空间复杂度还是满足O(n)的,当然也可以用两个指针分别指向要进行调整的两个结点,如上图分别指向 2 和 1, 4 和 1.
实现:
//store disorder nodes, most of the number is 4. vector<TreeNode*> outorder; //point to the last node of inorder sequence TreeNode *pre = NULL; void visitInorder(TreeNode* root){ if(root == NULL) return; if(root->left) visitInorder(root->left); if(pre == NULL) pre = root; else if(root->val < pre->val){ outorder.push_back(pre); outorder.push_back(root); } //move pre to the new tail. pre = root; if(root->right) visitInorder(root->right); } void recoverTree(TreeNode *root) { if( NULL == root ) return; visitInorder(root); if(outorder.size()) { swap(outorder[0]->val, outorder[outorder.size() - 1]->val); } }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。