algo-aha

分层遍历

• https://leetcode.com/problems/binary-tree-level-order-traversal/

vector<vector<int>> levelOrder(TreeNode* root) {
    vector<vector<int>> ans;
    queue<TreeNode *> q;
    if (root) q.push(root);
    while (!q.empty()) {
        vector<int> row;
        for (int sz = q.size(); sz > 0; sz--) {
            auto node = q.front(); q.pop();
            row.push_back(node->val);

            if (node->left) q.push(node->left);
            if (node->right) q.push(node->right);
        }
        ans.push_back(row);
    }
    return ans;
}

或两个队列换着用

vector<vector<int>> levelOrder(TreeNode* root) {
    vector<vector<int>> ans;
    vector<TreeNode *> curr;
    if (root) curr.push_back(root);
    while (!curr.empty()) {
        vector<int> row;
        vector<TreeNode *> next;
        for (auto node : curr) {
            row.push_back(node->val);
            
            if (node->left) next.push_back(node->left);
            if (node->right) next.push_back(node->right);
        }
        ans.push_back(row);
        swap(curr, next);
    }
    return ans;
}

扩展：之字形分层遍历

是不是完全二叉树

• https://leetcode.com/problems/check-completeness-of-a-binary-tree/

bool isCompleteTree(TreeNode* root) {
    queue<TreeNode *> q;
    q.push(root);

    // BFS，在弹出nullptr后不应再有实际节点
    bool seenNull = false;
    while (!q.empty()) {
        auto node = q.front(); q.pop();
        if (!node) {
            seenNull = true;
        } else {
            if (seenNull) return false;
            q.push(node->left);
            q.push(node->right);
        }
    }
    return true;
}

ref: 是不是二叉搜索树

分层反向编号的满二叉树，从根节点到本节点的路径

• https://leetcode.com/problems/path-in-zigzag-labelled-binary-tree/

inline int pow2(int n) {
    return 1 << n;
}

vector<int> pathInZigZagTree(int label) {
    // 第h层（0-based）的label范围[2^h..2^(h+1)-1]
    int h = 0;
    while (pow2(h+1) - 1 < label) {
        h++;
    }
    
    vector<int> ans;
    while (label) {
        ans.push_back(label);
        // 每层都与上一层方向相反
        label = (pow2(h) + pow2(h+1) - 1 - label) / 2;
        h--;
    }
    reverse(ans.begin(), ans.end());
    return ans;
}

同层节点用next指针连起来

• https://leetcode.com/problems/populating-next-right-pointers-in-each-node-ii/

Node* connect(Node *root) {
    Node nextRow(0); // 下层起点
    auto last = &nextRow;
    auto curr = root;
    while (curr) { // 遍历当前层，当前层已用next指针连接
        if (curr->left) {
            last->next = curr->left;
            last = curr->left;
        }
        if (curr->right) {
            last->next = curr->right;
            last = curr->right;
        }
        curr = curr->next;

        if (!curr) { 
            curr = nextRow.next;
            nextRow.next = NULL;
            last = &nextRow;
        }
    }
    return root;
}