溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
python完全二叉樹節(jié)點個數(shù)的示例分析，針對這個問題，這篇文章詳細介紹了相對應的分析和解答，希望可以幫助更多想解決這個問題的小伙伴找到更簡單易行的方法。
給出一個完全二叉樹，求出該樹的節(jié)點個數(shù)。
說明：
完全二叉樹的定義如下：在完全二叉樹中，除了最底層節(jié)點可能沒填滿外，其余每層節(jié)點數(shù)都達到最大值，并且最下面一層的節(jié)點都集中在該層最左邊的若干位置。若最底層為第 h 層，則該層包含 1~ 2h 個節(jié)點。
示例:
輸入:
1
/ \
2 3
/ \ /
4 5 6
輸出: 6解題思路：
1，遞歸遍歷整個二叉樹，這個方法可以優(yōu)化
2，計算左右子樹的高度l,r
A,如果l＝r 說明左子樹是滿二叉樹,節(jié)點數(shù)為 2^l-1，右子樹需要遞歸計算
B,如果l＝r+1 說明右子樹是滿二叉樹，節(jié)點數(shù)為2^r-1，左子樹需要遞歸計算
3，樹的節(jié)點數(shù)為 根（1）＋左子樹的節(jié)點數(shù)＋右子樹的節(jié)點數(shù)
/*** 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 =0for root!=nil{root=root.Leftl++}return l}
關于python完全二叉樹節(jié)點個數(shù)的示例分析問題的解答就分享到這里了，希望以上內(nèi)容可以對大家有一定的幫助，如果你還有很多疑惑沒有解開，可以關注億速云行業(yè)資訊頻道了解更多相關知識。
免責聲明：本站發(fā)布的內(nèi)容（圖片、視頻和文字）以原創(chuàng)、轉(zhuǎn)載和分享為主，文章觀點不代表本網(wǎng)站立場，如果涉及侵權(quán)請聯(lián)系站長郵箱：is@yisu.com進行舉報，并提供相關證據(jù)，一經(jīng)查實，將立刻刪除涉嫌侵權(quán)內(nèi)容。
