树的节点数
一句话说明
普通树直接递归计数，完全二叉树可以靠高度直接剪枝。
Go 代码：普通计数
func countNodes(root *TreeNode) int {
if root == nil {
return 0
}
return 1 + countNodes(root.Left) + countNodes(root.Right)
}Go 代码：完全二叉树优化
func countCompleteNodes(root *TreeNode) int {
if root == nil {
return 0
}
leftDepth := leftHeight(root.Left)
rightDepth := leftHeight(root.Right)
if leftDepth == rightDepth {
return (1 << leftDepth) + countCompleteNodes(root.Right)
}
return (1 << rightDepth) + countCompleteNodes(root.Left)
}
func leftHeight(node *TreeNode) int {
h := 0
for node != nil {
h++
node = node.Left
}
return h
}为什么能剪枝
完全二叉树某一侧如果已经是满二叉树，就能直接套公式，不用继续一层层数。