Commitb7f0e40

committed

Tree traversal add 145 postorder

1 parent82282bd commitb7f0e40Copy full SHA for b7f0e40

File tree

+76

-0

lines changed

+76

-0

lines changed

Lines changed: 36 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,36 @@`
	`1`	`+/**`
	`2`	`+ * Definition for a binary tree node.`
	`3`	`+ * function TreeNode(val) {`
	`4`	`+ * this.val = val;`
	`5`	`+ * this.left = this.right = null;`
	`6`	`+ * }`
	`7`	`+ */`
	`8`	`+/**`
	`9`	`+ *@param {TreeNode} root`
	`10`	`+ *@return {number[]}`
	`11`	`+ */`
	`12`	`+// looks like there is a better way to implement`
	`13`	`+varpostorderTraversal=function(root){`
	`14`	`+varresult=[];`
	`15`	`+if(!root)returnresult;`
	`16`	`+varstack=[root];`
	`17`	`+varpreVisitedNode=null;`
	`18`	`+`
	`19`	`+while(stack.length>0){`
	`20`	`+node=stack[stack.length-1];`
	`21`	`+if(!node.left&&!node.right\|\|`
	`22`	`+(preVisitedNode&&(preVisitedNode===node.right\|\|preVisitedNode===node.left))){`
	`23`	`+result.push(node.val);`
	`24`	`+preVisitedNode=stack.pop();`
	`25`	`+}else{`
	`26`	`+if(node.right){`
	`27`	`+stack.push(node.right);`
	`28`	`+}`
	`29`	`+if(node.left){`
	`30`	`+stack.push(node.left);`
	`31`	`+}`
	`32`	`+}`
	`33`	`+}`
	`34`	`+`
	`35`	`+returnresult;`
	`36`	`+};`

Lines changed: 1 addition & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -26,6 +26,7 @@ var preorderTraversal = function(root) {`
`26`	`26`	`};`
`27`	`27`
`28`	`28`	`// this is a more straightforward method, but slower than first one.`
	`29`	`+// stack tracks the node visit order`
`29`	`30`	`varpreorderTraversal=function(root){`
`30`	`31`	`if(!root)return[];`
`31`	`32`	`varresult=[];`

Lines changed: 18 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -29,3 +29,21 @@ var kthSmallest = function(root, k) {`
`29`	`29`	`}`
`30`	`30`	`}`
`31`	`31`	`};`
	`32`	`+`
	`33`	`+// second try`
	`34`	`+varkthSmallest=function(root,k){`
	`35`	`+varstack=[];`
	`36`	`+`
	`37`	`+while(root\|\|stack.length>0){`
	`38`	`+while(root){`
	`39`	`+stack.push(root);`
	`40`	`+root=root.left;`
	`41`	`+}`
	`42`	`+root=stack.pop();`
	`43`	`+k--;`
	`44`	`+if(k===0)returnroot.val;`
	`45`	`+root=root.right;`
	`46`	`+}`
	`47`	`+`
	`48`	`+return0;`
	`49`	`+};`

Lines changed: 20 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -25,3 +25,23 @@ var inorderTraversal = function(root) {`
`25`	`25`
`26`	`26`	`returnorder;`
`27`	`27`	`};`
	`28`	`+`
	`29`	`+// more concise and efficient`
	`30`	`+// as long as the left child is not empty, push it to the stack`
	`31`	`+// once left child reaches to the end (leaf), pop the last left, and visit,`
	`32`	`+// then assign its right node to be root, and repeat the process on current root (the right child)`
	`33`	`+varinorderTraversal=function(root){`
	`34`	`+varstack=[];`
	`35`	`+varorder=[];`
	`36`	`+`
	`37`	`+while(root\|\|stack.length>0){`
	`38`	`+while(root){`
	`39`	`+stack.push(root);`
	`40`	`+root=root.left;`
	`41`	`+}`
	`42`	`+varnode=stack.pop();`
	`43`	`+order.push(node.val);`
	`44`	`+root=node.right;`
	`45`	`+}`
	`46`	`+returnorder;`
	`47`	`+};`

Lines changed: 1 addition & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -172,4 +172,5 @@`
`172`	`172`	`*[115. Distinct Subsequences](https://leetcode.com/problems/distinct-subsequences/) -[Solution](./Hard/115-distinctSubsequences.js)`
`173`	`173`	`*[123. Best Time to Buy and Sell Stock III](https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/) -[Solution](./Hard/123-bestTimeBuySellStockIII.js)`
`174`	`174`	`*[132. Palindrome Partitioning II](https://leetcode.com/problems/palindrome-partitioning-ii/) -[Solution](./Hard/132-palindromePartitioningII.js)`
	`175`	`+*[145. Binary Tree Postorder Traversal](https://leetcode.com/problems/binary-tree-postorder-traversal/) -[Solution](./Hard/145-binaryTreePostorder.js)`
`175`	`176`	`*[154.Find Minimum in Rotated Sorted Array II](https://leetcode.com/problems/find-minimum-in-rotated-sorted-array-ii/) -[Solution](./Hard/154-findMinimumInRotatedSortedArray-II.js)`

Comments

(0)