Commit2f314fe

applewjg

committed

uadd morris For RecoverBST

Change-Id: I44eaeb179d02187b034f3ae234df596e8cfdf934

1 parent493065b commit2f314feCopy full SHA for 2f314fe

File tree

1 file changed

+36

-1

lines changed

RecoverBinarySearchTree.java

1 file changed

+36

-1

lines changed

`‎RecoverBinarySearchTree.java`

Lines changed: 36 additions & 1 deletion

Original file line number	Diff line number	Diff line change
`@@ -13,7 +13,7 @@ A solution using O(n) space is pretty straight forward. Could you devise a const`
`13`	`13`	`Solution: 1. recursive solution. O(n) space. get inorder list first.`
`14`	`14`	`2. recursive solution. O(n) space. with only auxiliary two pointers.`
`15`	`15`	`3. Use a stack. Iteration.`
`16`		`- 4.TBD.Morris inorder traversal. O(1) space. with only auxiliary two pointers.`
	`16`	`+ 4. Morris inorder traversal. O(1) space. with only auxiliary two pointers.`
`17`	`17`	`*/`
`18`	`18`
`19`	`19`	`/**`
`@@ -90,4 +90,39 @@ public void recoverTree_3(TreeNode root) {`
`90`	`90`	`first.val =second.val;`
`91`	`91`	`second.val =tmp;`
`92`	`92`	`}`
	`93`	`+`
	`94`	`+publicvoidrecoverTree_4(TreeNoderoot) {`
	`95`	`+if (root ==null)return;`
	`96`	`+TreeNodecur =root,pre =null,first =null,second =null;`
	`97`	`+while (cur !=null) {`
	`98`	`+if (cur.left ==null) {`
	`99`	`+if (pre !=null &&pre.val >cur.val) {`
	`100`	`+if (first ==null)first =pre;`
	`101`	`+second =cur;`
	`102`	`+ }`
	`103`	`+pre =cur;`
	`104`	`+cur =cur.right;`
	`105`	`+ }else {`
	`106`	`+TreeNodenode =cur.left;`
	`107`	`+while (node.right !=null &&node.right !=cur)`
	`108`	`+node =node.right;`
	`109`	`+if (node.right !=null) {`
	`110`	`+if (pre !=null &&pre.val >cur.val) {`
	`111`	`+if (first ==null)first =pre;`
	`112`	`+second =cur;`
	`113`	`+ }`
	`114`	`+pre =cur;`
	`115`	`+node.right =null;`
	`116`	`+cur =cur.right;`
	`117`	`+ }else {`
	`118`	`+node.right =cur;`
	`119`	`+cur =cur.left;`
	`120`	`+ }`
	`121`	`+ }`
	`122`	`+ }`
	`123`	`+if (first ==null)return;`
	`124`	`+inttmp =first.val;`
	`125`	`+first.val =second.val;`
	`126`	`+second.val =tmp;`
	`127`	`+ }`
`93`	`128`	`}`

0 commit comments

Comments

(0)

Movatterモバイル変換

Navigation Menu

Search code, repositories, users, issues, pull requests...

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Uh oh!

Commit2f314fe

File tree

1 file changed

1 file changed

`‎RecoverBinarySearchTree.java`

0 commit comments