Commit2e8bd9e

authored

Update Convert Binary Search Tree to Sorted Doubly Linked List.java

1 parent328a063 commit2e8bd9eCopy full SHA for 2e8bd9e

File tree

+25

-17

lines changed

+25

-17

lines changed

Lines changed: 25 additions & 17 deletions

Original file line number	Diff line number	Diff line change
`@@ -20,27 +20,35 @@ public Node(int _val,Node _left,Node _right) {`
`20`	`20`	`*/`
`21`	`21`
`22`	`22`	`classSolution {`
`23`		`-Nodeprev;`
`24`	`23`	`publicNodetreeToDoublyList(Noderoot) {`
`25`	`24`	`if (root ==null) {`
`26`	`25`	`returnroot;`
`27`	`26`	`}`
`28`		`-Nodedummy =newNode(0);`
`29`		`-prev =dummy;`
`30`		`-helper(root);`
`31`		`-prev.right =dummy.right;`
`32`		`-dummy.right.left =prev;`
`33`		`-returndummy.right;`
`34`		`- }`
`35`		`-`
`36`		`-privatevoidhelper(Noderoot) {`
`37`		`-if (root ==null) {`
`38`		`-return;`
	`27`	`+Stack<Node>stack =newStack<>();`
	`28`	`+while (root !=null) {`
	`29`	`+stack.push(root);`
	`30`	`+root =root.left;`
	`31`	`+ }`
	`32`	`+Nodehead =null;`
	`33`	`+Nodeprev =null;`
	`34`	`+while (!stack.isEmpty()) {`
	`35`	`+Noderemoved =stack.pop();`
	`36`	`+NoderightNode =removed.right;`
	`37`	`+while (rightNode !=null) {`
	`38`	`+stack.push(rightNode);`
	`39`	`+rightNode =rightNode.left;`
	`40`	`+ }`
	`41`	`+if (head ==null) {`
	`42`	`+head =removed;`
	`43`	`+ }`
	`44`	`+if (prev !=null) {`
	`45`	`+prev.right =removed;`
	`46`	`+ }`
	`47`	`+removed.left =prev;`
	`48`	`+prev =removed;`
`39`	`49`	`}`
`40`		`-helper(root.left);`
`41`		`-prev.right =root;`
`42`		`-root.left =prev;`
`43`		`-prev =root;`
`44`		`-helper(root.right);`
	`50`	`+head.left =prev;`
	`51`	`+prev.right =head;`
	`52`	`+returnhead;`
`45`	`53`	`}`
`46`	`54`	`}`

Comments

(0)