[LeetCode] 99. Recover Binary Search Tree
发布时间:2020-12-14 03:51:00 所属栏目:大数据 来源:网络整理
导读:Two elements of a binary search tree (BST) are swapped by mistake. Recover the tree without changing its structure. Example 1: Input: [1,3,null,2]? 1? /?3? ? 2Output: [3,1,2]? 3? /?1? ? 2 Example 2: Input: [3,4,2] 3 / 1 4? /? 2Output: [2,3
Two elements of a binary search tree (BST) are swapped by mistake. Recover the tree without changing its structure. Example 1: Input: [1,3,null,2] ? 1 ? / ?3 ? ? 2 Output: [3,1,2] ? 3 ? / ?1 ? ? 2 Example 2: Input: [3,4,2] 3 / 1 4 ? / ? 2 Output: [2,3] 2 / 1 4 ? / ?3 Follow up:
? 因为是BST,所以需要用到inorder traversal来判断是哪两个点需要交换,因此,我们用pre来记录之前遍历的node,然后第一个pre.val > node.val,表明pre为第一个不对的node. 然后通过同样的道理,如果第一个找到了,我们就不断通过pre.val > node.val 这一条件将node更新为第二个点.最后将第一个点和第二个点交换,即可. ? 1. Constriants 1) None => Nothing ? 2. Ideas Inorder traversal? ? ?T; O(n)? ? ?S; O(1) ? 3. Code class Solution: def recoverBST(self,root): ans = [None,None,None] #firNode,secNode,pre def helper(node): if not node: return helper(node.left) if not ans[0] and ans[2] and ans[2].val > node.val: ans[0] = ans[2] if ans[0] and ans[2] and ans[2].val > node.val: ans[0] = node ans[2] = node helper(node.right) helper(root) ans[0].val,ans[1].val = ans[1].val,ans[0].val ? 4. Test cases 1)? Example 1: Input: [1,3] 2 / 1 4 ? / ?3 (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |
相关内容
- java – Spring启动CommandLineRunner异常处理
- lua html式解析
- 双11技术专题 | 如何快速挖掘“非结构化数据”金矿
- 《程序员的第一年》---------- 数据挖掘之数据处理(C#基于
- delphi中cxgrid和数据库搭配的基本应用
- 使用tolua++编译pkg,从而创建自定义类让Lua脚本使用
- perl – ExtUtils :: MakeMaker:如何为测试和/或安装指定二
- hdu 1402 A * B Problem Plus (FFT + 大数相乘)
- delphi – 如何将多个文件扩展名传递给TDirectory.GetFiles
- Perl正则表达式中的括号有什么作用?