Commit4f6bf5e

applewjg

committed

add inorder solution

Change-Id: I845e188989bfd6ba1f59f4ad1bf6992023220b57

1 parentb9f7dfb commit4f6bf5eCopy full SHA for 4f6bf5e

File tree

+19

-2

lines changed

+19

-2

lines changed

Lines changed: 19 additions & 2 deletions

Original file line number	Diff line number	Diff line change
`@@ -7,8 +7,10 @@`
`7`	`7`	`Notes:`
`8`	`8`	`Given an array where elements are sorted in ascending order, convert it to a height balanced BST.`
`9`	`9`
`10`		`- Solution: Recursion.`
	`10`	`+ Solution: Recursion. 1. preorder`
	`11`	`+ 2. inorder`
`11`	`12`	`*/`
	`13`	`+`
`12`	`14`	`/**`
`13`	`15`	`* Definition for binary tree`
`14`	`16`	`* public class TreeNode {`
`@@ -19,7 +21,7 @@`
`19`	`21`	`* }`
`20`	`22`	`*/`
`21`	`23`	`publicclassSolution {`
`22`		`-publicTreeNodesortedArrayToBST(int[]num) {`
	`24`	`+publicTreeNodesortedArrayToBST_1(int[]num) {`
`23`	`25`	`returnsortedArrayToBSTRe(num,0,num.length -1);`
`24`	`26`	`}`
`25`	`27`	`publicTreeNodesortedArrayToBSTRe(int[]num,intleft,intright) {`
`@@ -31,4 +33,19 @@ public TreeNode sortedArrayToBSTRe(int[] num, int left, int right) {`
`31`	`33`	`node.right =sortedArrayToBSTRe(num,mid +1,right);`
`32`	`34`	`returnnode;`
`33`	`35`	`}`
	`36`	`+publicTreeNodesortedArrayToBST(int[]num) {`
	`37`	`+int[]curidx =newint[1];`
	`38`	`+curidx[0] =0;`
	`39`	`+returnsortedArrayToBSTRe1(num,num.length,curidx);`
	`40`	`+ }`
	`41`	`+publicTreeNodesortedArrayToBSTRe1(int[]num,intlen,int[]curidx) {`
	`42`	`+if (len ==0)returnnull;`
	`43`	`+if (len ==1)returnnewTreeNode(num[curidx[0]++]);`
	`44`	`+intmid =len /2;`
	`45`	`+TreeNodeleft =sortedArrayToBSTRe1(num,mid,curidx);`
	`46`	`+TreeNodenode =newTreeNode(num[curidx[0]++]);`
	`47`	`+node.left =left;`
	`48`	`+node.right =sortedArrayToBSTRe1(num,len -1 -mid,curidx);`
	`49`	`+returnnode;`
	`50`	`+ }`
`34`	`51`	`}`

Comments

(0)