给出一个完全二叉树,求出该树的节点个数。
说明:
完全二叉树的定义如下:在完全二叉树中,除了最底层节点可能没填满外,其余每层节点数都达到最大值,并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层,则该层包含 1~ 2h 个节点。
示例:
输入:
1
/ \
2 3
/ \ /
4 5 6
输出: 6
解题思路:
1,递归遍历整个二叉树,这个方法可以优化
2,计算左右子树的高度l,r
A,如果l=r 说明左子树是满二叉树,节点数为 2^l-1,右子树需要递归计算
B,如果l=r+1 说明右子树是满二叉树,节点数为2^r-1,左子树需要递归计算
3,树的节点数为 根(1)+左子树的节点数+右子树的节点数
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func countNodes(root *TreeNode) int {
if root==nil{
return 0
}
l:=depth(root.Left)
r:=depth(root.Right)
if l==r{
return 1<<l+countNodes(root.Right)
}
return 1<<r+countNodes(root.Left)
}
func depth(root*TreeNode) uint{
if root==nil{
return 0
}
var l uint =0
for root!=nil{
root=root.Left
l++
}
return l
}
本文分享自 golang算法架构leetcode技术php 微信公众号,前往查看
如有侵权,请联系 cloudcommunity@tencent.com 删除。
本文参与 腾讯云自媒体同步曝光计划 ,欢迎热爱写作的你一起参与!