0222. Count Complete Tree Nodes | LeetCode Cookbook

[halfrost]

https://books.halfrost.com/leetcode/ChapterFour/0200~0299/0222.Count-Complete-Tree-Nodes/

[hanlins]

这道题后来补充说要设计一个小于 O(n) 复杂度的算法，所以是要利用完全二叉树的性质的。

Design an algorithm that runs in less than O(n) time complexity.

我是通过比较二叉树最左和最右节点是不是在同一个level上，如果是的话利用完全二叉树性质就可以直接返回大小 2^h-1，如果不是的话再各自递归。

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func countNodes(root *TreeNode) int {
    return smartCnt(root, 0, 0)
}

func smartCnt(node *TreeNode, ld, rd int) (res int) {
    if node == nil {
        return 0
    }
    if ld == 0 {
        for pt := node; pt != nil; pt = pt.Left { ld++ }
    }
    if rd == 0 {
        for pt := node; pt != nil; pt = pt.Right { rd++ }
    }
    if ld == rd {
        return (1 << ld) - 1
    }
    return smartCnt(node.Left, ld-1, 0) + smartCnt(node.Right, 0, rd-1) + 1
}