python中完全二叉树节点个数的示例分析

python完全二叉树节点个数的示例分析，针对这个问题，这篇文章详细介绍了相对应的分析和解答，希望可以帮助更多想解决这个问题的小伙伴找到更简单易行的方法。

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

说明：

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

关于python完全二叉树节点个数的示例分析问题的解答就分享到这里了，希望以上内容可以对大家有一定的帮助，如果你还有很多疑惑没有解开，可以关注行业资讯频道了解更多相关知识。

python中完全二叉树节点个数的示例分析

相关推荐