golang刷leetcode 二叉树（6）完全二叉树点个数

golangLeetcode

发布于 2022-08-02 16:03:31

1710

发布于 2022-08-02 16:03:31

文章被收录于专栏：golang算法架构leetcode技术php

给出一个完全二叉树，求出该树的节点个数。

说明：

完全二叉树的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 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
}

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2019-04-03，如有侵权请联系 cloudcommunity@tencent.com 删除

二叉树