第87题不需要遍历利用满二叉树性质 O(层数^2)

[Dongyang666]

    public int nodeNum(TreeNode root) {
        if (root == null) return 0;
	return nodeNum(root, 1, mostLeftHeight(root, 1));
    }
    public int nodeNum(TreeNode root, int l, int h) {
	if (l == h) return 1;
	// 不满的那一枝在右边 则可以直接计算左边节点的数量
	if (mostLeftHeight(root.right, l + 1) == h) {
		return (1 << (h - l)) + nodeNum(root.right, l + 1, h);
	} else {
		// 不满的那一枝在左边 可直接计算右边节点数量
		return (1 << (h - l - 1) + nodeNum(root.left, l + 1, h));
	}
    }

	public int mostLeftHeight(TreeNode root, int h) {
		while (root != null) {
			h++;
			root = root.left;
		}
		return h - 1;
	}