Commitab002e7

authored

Merge pull requestyoungyangyang04#420 from betNevS/master

增加 0222.完全二叉树的节点个数 go版（新增利用完全二叉树特性的递归解法）

2 parents0135feb +a85e410 commitab002e7Copy full SHA for ab002e7

File tree

+47

-0

lines changed

+47

-0

lines changed

Lines changed: 24 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -335,6 +335,30 @@ func countNodes(root *TreeNode) int {`
`335`	`335`	`}`
`336`	`336`	```
`337`	`337`
	`338`	`+利用完全二叉树特性的递归解法`
	`339`	+```go
	`340`	`+funccountNodes(root *TreeNode)int {`
	`341`	`+if root ==nil {`
	`342`	`+return0`
	`343`	`+ }`
	`344`	`+leftH,rightH:=0,0`
	`345`	`+leftNode:= root.Left`
	`346`	`+rightNode:= root.Right`
	`347`	`+for leftNode !=nil {`
	`348`	`+ leftNode = leftNode.Left`
	`349`	`+ leftH++`
	`350`	`+ }`
	`351`	`+for rightNode !=nil {`
	`352`	`+ rightNode = rightNode.Right`
	`353`	`+ rightH++`
	`354`	`+ }`
	`355`	`+if leftH == rightH {`
	`356`	`+return (2 << leftH) -1`
	`357`	`+ }`
	`358`	`+returncountNodes(root.Left) +countNodes(root.Right) +1`
	`359`	`+}`
	`360`	+```
	`361`	`+`
`338`	`362`
`339`	`363`
`340`	`364`	`#"diff-d8f1a5972311065e82c213e0f34e1ebad39b2d9ceb8281811ad8225f38bc3099-empty-empty-0" data-selected="false" role="gridcell" tabindex="-1" valign="top" colSpan="4">`

Lines changed: 23 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -350,6 +350,29 @@ class Solution:`
`350`	`350`
`351`	`351`	```
`352`	`352`	`Go：`
	`353`	`+`
	`354`	+```go
	`355`	`+funcbinaryTreePaths(root *TreeNode) []string {`
	`356`	`+res:=make([]string,0)`
	`357`	`+vartravelfunc(node *TreeNode, sstring)`
	`358`	`+ travel =func(node *TreeNode, sstring) {`
	`359`	`+if node.Left ==nil && node.Right ==nil {`
	`360`	`+v:= s + strconv.Itoa(node.Val)`
	`361`	`+ res =append(res, v)`
	`362`	`+return`
	`363`	`+ }`
	`364`	`+ s = s + strconv.Itoa(node.Val) +"->"`
	`365`	`+if node.Left !=nil {`
	`366`	`+travel(node.Left, s)`
	`367`	`+ }`
	`368`	`+if node.Right !=nil {`
	`369`	`+travel(node.Right, s)`
	`370`	`+ }`
	`371`	`+ }`
	`372`	`+travel(root,"")`
	`373`	`+return res`
	`374`	`+}`
	`375`	+```
`353`	`376`
`354`	`377`	`#"diff-b1466619a5bed02334926f41d969556c8dd67411a1f02f5610319b55568f0c3f-355-378-0" data-selected="false" role="gridcell" tabindex="-1" valign="top">355`	`378`	`1.递归版本`

Comments

(0)