這題真的把遞歸思想用到極致了上遥。搏屑。挺難的。最好能復習一下.
要體會它的復雜度是 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的遞歸暑中、非遞歸實現(xiàn)
另外，我想起上次被問道深度遍歷(DFS)二叉樹的非遞歸方式用什么數(shù)據(jù)結(jié)構(gòu)實現(xiàn)鲫剿，我愣了一下鳄逾，我知道是用棧，但其實我不知道具體怎么實現(xiàn)灵莲。今天復習了一下雕凹。
- 二叉樹BFS的非遞歸和遞歸實現(xiàn)
前者就是用LinkedList嘛，后者就是用一個List<List<TreeNode>>政冻。今天都寫了一遍枚抵。 - 二叉樹DFS的的遞歸和非遞歸實現(xiàn)
前者就是三種order的簡單實現(xiàn)侠驯，后者用棧魔熏，先把right subtree的node push進去, 參考這里：
//深度優(yōu)先搜索
//利用棧变秦，現(xiàn)將右子樹壓棧再將左子樹壓棧
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 << ' ';的位置移動一下就好了。
