005.完全二叉树的节点个数

• 222.完全二叉树的节点个数
  • 以普通二叉树看待
    • 递归
    • 迭代
  • 以完全二叉树看待
    • 满二叉树：节点个数 = 2^树深度 - 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
	}
	left, right := root.Left, root.Right
	leftDepth, rightDepth := 0, 0
	for left != nil {
		leftDepth++
		left = left.Left
	}
	for right != nil {
		rightDepth++
		right = right.Right
	}
	if leftDepth == rightDepth {
		// 满二叉树
		return (2 << leftDepth) - 1
	}
	return 1 + countNodes(root.Left) + countNodes(root.Right)
}

或者

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
var (
	h int // 整棵完全二叉树的高度
)
 
func countNodes(root *TreeNode) int {
	if root == nil {
		return 0
	}
	h = mostLeft(root, 1)
	return process(root, 1)
}
 
// cur: 当前来到的节点
// level: cur 在第几层
// 返回 cur 这棵子树上有多少节点
func process(cur *TreeNode, level int) int {
	if level == h {
		return 1
	}
	if mostLeft(cur.Right, level+1) == h {
		// cur 右树上的最左节点，扎到了最深层
		// 说明 cur.Left 是满二叉树
		// 1<<(h-level)：左子树节点数 + 1（当前节点）
		return 1<<(h-level) + process(cur.Right, level+1)
	} else {
		// cur 右树上的最左节点，没扎到最深层
		// 说明 cur.Right 是满二叉树
		return 1<<(h-level-1) + process(cur.Left, level+1)
	}
}
 
// 当前节点是 cur，它在第 level 层
// 返回从 cur 开始不停往左，能扎到几层
func mostLeft(cur *TreeNode, level int) int {
	for cur != nil {
		level++
		cur = cur.Left
	}
	return level - 1
}

• 时间复杂度：$O(log{n}^2)$
  • 设树高为 $h$，则 $h=lo{g}_2^n$，每来到一层，往下扎到 $h$，共 $h$ 层，所以时间复杂度是 $O(h^2)$
• 空间复杂度：$O(lo{g}^n)$
  • 递归的函数调用栈空间，最大压到 $h$