222.[R]Count Complete Tree Nodes

这题真的把递归思想用到极致了。。挺难的。最好能复习一下.
要体会它的复杂度是 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)二叉树的非递归方式用什么数据结构实现，我愣了一下，我知道是用栈，但其实我不知道具体怎么实现。今天复习了一下。

1. 二叉树BFS的非递归和递归实现
   前者就是用LinkedList嘛，后者就是用一个List<List<TreeNode>>。今天都写了一遍。
2. 二叉树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 << ' ';的位置移动一下就好了。

---