Commitdc4fa31

committed

another iterative version of preorder traversal

1 parenta05f3b5 commitdc4fa31Copy full SHA for dc4fa31

File tree

+17

-1

lines changed

+17

-1

lines changed

Lines changed: 17 additions & 1 deletion

Original file line number	Diff line number	Diff line change
`@@ -7,7 +7,7 @@`
`7`	`7`	`importclasses.TreeNode;`
`8`	`8`
`9`	`9`	`publicclassBinaryTreePreorderTraversal {`
`10`		`-publicList<Integer>preorderTraversal_iterative(TreeNoderoot) {`
	`10`	`+publicList<Integer>preorderTraversal_iterative_original(TreeNoderoot) {`
`11`	`11`	`List<Integer>list =newArrayList();`
`12`	`12`	`Stack<TreeNode>stack =newStack();`
`13`	`13`	`if(root ==null)returnlist;`
`@@ -21,6 +21,22 @@ public List<Integer> preorderTraversal_iterative(TreeNode root) {`
`21`	`21`	`returnlist;`
`22`	`22`	`}`
`23`	`23`
	`24`	`+publicList<Integer>preorderTraversal_iterative_online(TreeNoderoot) {`
	`25`	`+List<Integer>list =newArrayList();`
	`26`	`+Stack<TreeNode>stack =newStack();`
	`27`	`+if(root ==null)returnlist;`
	`28`	`+while(root !=null \|\| !stack.isEmpty()){`
	`29`	`+if(root !=null){`
	`30`	`+list.add(root.val);`
	`31`	`+stack.push(root);`
	`32`	`+root =root.left;`
	`33`	`+ }else {`
	`34`	`+root =stack.pop().right;`
	`35`	`+ }`
	`36`	`+ }`
	`37`	`+returnlist;`
	`38`	`+ }`
	`39`	`+`
`24`	`40`	`//recursive solution is really trivial:`
`25`	`41`	`publicList<Integer>preorderTraversal_recursive(TreeNoderoot) {`
`26`	`42`	`List<Integer>list =newArrayList();`

Comments

(0)