Count Complete Tree Nodes -- LeetCode

Given a complete binary tree, count the number of nodes.

Definition of a complete binary tree from Wikipedia:
In a complete binary tree every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. It can have between 1 and 2h nodes inclusive at the last level h.

思路：解决这个问题，我们首先要获得树的最大深度。对于一颗空的树，其深度为-1，对于只有一个根节点的树，其深度为0，以此类推。

之后，我们比较左子树和右子树的深度。这里只有两种情况，两颗子树的深度相等，或者左子树的深度比右子树的深度大1。

当两颗子树深度相等时，我们知道当前这棵树最底层的叶子结点在两棵子树中都有，因此左子树是完全二叉树。于是我们可以根据深度计算出左子树的节点数加1（包含当前树的根节点），然后通过递归计算右子树的节点数。
当两颗深度不想等时，我们知道当前这棵树最底层的叶子结点只在左子树中，因此右子树是完全二叉树。于是我们可以根据深度计算出右子树的节点数加一（包含当前树的根节点），然后通过递归计算左子树的节点数。

我们最多进行O(logn)次递归，每次递归时都需要计算深度，复杂度O(logn)，总复杂度是O(logN*logN)。

 1 /**
 2  * Definition for a binary tree node.
 3  * struct TreeNode {
 4  *     int val;
 5  *     TreeNode *left;
 6  *     TreeNode *right;
 7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 8  * };
 9  */
10 class Solution {
11 public:
12     int depth(TreeNode* root) {
13         return root == NULL ? -1 : 1 + depth(root->left);
14     }
15     int countNodes(TreeNode* root) {
16         int dep = depth(root);
17         if (dep < 1) return dep + 1;
18         int rightChildDepth = depth(root->right);
19         if (dep == rightChildDepth + 1) return (1 << dep) + countNodes(root->right);
20         return (1 << (rightChildDepth + 1)) + countNodes(root->left);
21     }
22 };

Count Complete Tree Nodes -- LeetCode

相关推荐