Commit891bf6a

xeniaxie(xl)

committed

669修剪二叉搜索树JavaScript版本

1 parent53ce92f commit891bf6aCopy full SHA for 891bf6a

File tree

+53

-0

lines changed

+53

-0

lines changed

Lines changed: 53 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -289,6 +289,59 @@ Go：`
`289`	`289`
`290`	`290`
`291`	`291`
	`292`	`+JavaScript版本：`
	`293`	`+迭代：`
	`294`	+```js
	`295`	`+vartrimBST=function(root,low,high) {`
	`296`	`+if(root===null) {`
	`297`	`+returnnull;`
	`298`	`+ }`
	`299`	`+while(root!==null&&(root.val<low\|\|root.val>high)) {`
	`300`	`+if(root.val<low) {`
	`301`	`+ root=root.right;`
	`302`	`+ }else {`
	`303`	`+ root=root.left;`
	`304`	`+ }`
	`305`	`+ }`
	`306`	`+let cur= root;`
	`307`	`+while(cur!==null) {`
	`308`	`+while(cur.left&&cur.left.val<low) {`
	`309`	`+cur.left=cur.left.right;`
	`310`	`+ }`
	`311`	`+ cur=cur.left;`
	`312`	`+ }`
	`313`	`+ cur= root;`
	`314`	`+//判断右子树大于high的情况`
	`315`	`+while(cur!==null) {`
	`316`	`+while(cur.right&&cur.right.val>high) {`
	`317`	`+cur.right=cur.right.left;`
	`318`	`+ }`
	`319`	`+ cur=cur.right;`
	`320`	`+ }`
	`321`	`+return root;`
	`322`	`+};`
	`323`	+```
	`324`	`+`
	`325`	`+递归：`
	`326`	+```js
	`327`	`+vartrimBST=function (root,low,high) {`
	`328`	`+if(root===null) {`
	`329`	`+returnnull;`
	`330`	`+ }`
	`331`	`+if(root.val<low) {`
	`332`	`+let right=trimBST(root.right,low,high);`
	`333`	`+return right;`
	`334`	`+ }`
	`335`	`+if(root.val>high) {`
	`336`	`+let left=trimBST(root.left,low,high);`
	`337`	`+return left;`
	`338`	`+ }`
	`339`	`+root.left=trimBST(root.left,low,high);`
	`340`	`+root.right=trimBST(root.right,low,high);`
	`341`	`+return root;`
	`342`	`+ }`
	`343`	+```
	`344`	`+`
`292`	`345`
`293`	`346`	`-----------------------`
`294`	`347`	`* 作者微信：[程序员Carl](https://mp.weixin.qq.com/s/b66DFkOp8OOxdZC_xLZxfw)`

Comments

(0)