这题真的把递归思想用到极致了。。挺难的。最好能复习一下.
要体会它的复杂度是 O(log(n)^2)。
recursive:
class Solution {
int height(TreeNode root) {
return root == null ? -1 : 1 + height(root.left);
}
public int countNodes(TreeNode root) {
int h = height(root);
return h < 0 ? 0 :
height(root.right) == h-1 ? (1 << h) + countNodes(root.right)
: (1 << h-1) + countNodes(root.left);
}
}
iterative version:
private int height(TreeNode node) {
return node == null ? -1 : height(node.left) + 1;
}
public int countNodes(TreeNode root) {
int h = height(root);
int cnt = 0;
while (root != null) {
if (height(root.right) == h - 1) {
cnt += 1 << (h);
root = root.right;
} else {
cnt += 1 << (h - 1);
root = root.left;
}
h--;
}
return cnt;
}
20180120REVIEW
今天又把用LinkedList的bfs、递归的bfs（实际上利用的是dfs，得出答案是bfs的答案的那种）和最普通的dfs都复习了一遍，但毫无疑问上面三种都是TLE的。
感觉这题挺难的。对于上面的第一种递归写法，写成这样的话会好理解一些：
//4. use height
int height(TreeNode root) {
//这里最后算出来的高度比真正高度小1
return root == null ? -1 : 1 + height(root.left);
}
public int countNodes(TreeNode root) {
//h 是root的高度-1
int rootHeight = height(root);
//相当于判空
if (rootHeight == -1) {
return 0;
}
//right subtree的高度是root高度-2，说明最后一层的node没有蔓延到right subtree，
// 说明right subtree是真实高度为rootHeight + 1 -2 = rootHeight - 1的 complete binary tree
if (height(root.right) == rootHeight - 2) {
return countNodes(root.left) + (1 << rootHeight - 1) - 1 + 1;//(2^h - 1，+1是算上rootNode)
} else {
return countNodes(root.right) + (1 << rootHeight);
}
}
二叉树的BFS/DFS的递归、非递归实现
另外，我想起上次被问道深度遍历(DFS)二叉树的非递归方式用什么数据结构实现，我愣了一下，我知道是用栈，但其实我不知道具体怎么实现。今天复习了一下。
- 二叉树BFS的非递归和递归实现
前者就是用LinkedList嘛，后者就是用一个List<List<TreeNode>>。今天都写了一遍。 - 二叉树DFS的的递归和非递归实现
前者就是三种order的简单实现，后者用栈，先把right subtree的node push进去, 参考这里：
//深度优先搜索
//利用栈，现将右子树压栈再将左子树压栈
void DepthFirstSearch(BitNode *root)
{
stack<BitNode*> nodeStack;
nodeStack.push(root);
while (!nodeStack.empty())
{
BitNode *node = nodeStack.top();
cout << node->data << ' ';
nodeStack.pop();
if (node->right)
{
nodeStack.push(node->right);
}
if (node->left)
{
nodeStack.push(node->left);
}
}
}
可以看出上面是preOrder，inOrder和postOrder的话把 cout << node->data << ' ';的位置移动一下就好了。
