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 트리의 비귀속 방식이 어떤 데이터 구조로 이루어졌는지 물어봤던 기억이 떠올라서 멍하니 창고로 이루어진 건 알지만 구체적으로 어떻게 이루어졌는지 모르겠어요.오늘 복습을 했습니다.

두 갈래 나무 BFS의 비귀속과 귀속을 실현하는 전자는 LinkedList를 사용하고, 후자는 List>를 사용한다.오늘 다 썼는데..

이차수 DFS의 귀속과 비귀속 실현은 전자는 세 가지order의 간단한 실현이다. 후자는 창고를 사용하고 먼저 right subtree의 node push를 들어가서 여기를 참고한다

// 
// ， 
void DepthFirstSearch(BitNode *root)
{
    stack 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의 말은coutdata<>입니다.자리를 옮기면 돼요.