剑指offer - 从上到下打印二叉树

题目

1、不分行从上到下打印二叉树

struct BinaryTreeNode {
    int m_nValue;
    BinaryTreeNode *m_pLeft;
    BinaryTreeNode *m_pRight;
};

从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。例如，输入图4.6中的二叉树，则依次打印出8，6，10，5，7，9，11.

2.png

分析

因为按层打印的顺序决定了先打印根结点，所以我们从树的根结点开始分析。

为了能够打印值为8的结点的两个子结点，我们应该在遍历到该结点时把值为6和值为10的两个结点保存到队列里，那么现在队列内就有两个结点了。

按照从左到右打印的要求，我们先取出值为6的结点，打印出6之后，把它的子结点5和7放入队列。接下来取值为10的结点，然后把子结点9和11放入队列。典型的先进先出，配合队列完美的实现层级打印操作

总结：每次打印一个结点的时候，如果该结点有子结点，则把该结点的子结点放到队列的末尾。接下来从队列的头部取出最早进入队列的结点，重复前面的打印操作，直到队列中所有的结点都被打印出来

算法实现

#include <iostream>
#include <deque>
using namespace std;

struct BinaryTreeNode {
    int m_nValue;
    BinaryTreeNode *m_pLeft;
    BinaryTreeNode *m_pRight;
};

void PrintFromTopToBottom(BinaryTreeNode *pRoot) {
    if (pRoot == nullptr)
        return;

    deque<BinaryTreeNode *> dequeTreeNode;

    // 入队列
    dequeTreeNode.push_back(pRoot);

    while (dequeTreeNode.size()) {
        // 获取第一个结点
        BinaryTreeNode *node = dequeTreeNode.front();
        // 第一个结点出队列
        dequeTreeNode.pop_front();

        // 打印结点值
        printf("%d", node->m_nValue);

        // 左子结点存在入队列
        if (node->m_pLeft) {
            dequeTreeNode.push_back(node->m_pLeft);
        }

        // 右子结点存在入队列
        if (node->m_pRight) {
            dequeTreeNode.push_back(node->m_pRight);
        }
    }
}

2、分行从上到下打印二叉树

从上到下按层打印二叉树，同一层的结点按从左到右的顺序打印，每一层打印到一行。例如下：

8
6 10
5 7 9 11

算法实现

void Print(BinaryTreeNode *pRoot) {
    if (pRoot == nullptr)
        return;

    queue<BinaryTreeNode *> nodes;
    nodes.push(pRoot);

    int nextLevel = 0;
    int toBePrinted = 1;

    while (!nodes.empty()) {
        BinaryTreeNode *pNode = nodes.front();
        printf("%d", pNode->m_nValue);

        if (pNode->m_pLeft != nullptr) {
            nodes.push(pNode->m_pLeft);
            ++nextLevel;
        }

        if (pNode->m_pRight != nullptr) {
            nodes.push(pNode->m_pRight);
            ++nextLevel;
        }
        nodes.pop();
        --toBePrinted;

        if (toBePrinted == 0) {
            printf("\n");
            toBePrinted = nextLevel;
            nextLevel = 0;
        }
    }
}

在上述代码中，变量toBePrinted表示在当前层中还没有打印的结点数，而变量nextLevel表示下一层的结点数。如果一个结点有子结点，则每把一个子结点加入队列，同时把变量nextLevel加1。每打印一个结点，toBePrinted减1。当toBePrinted变成0时，表示当前层的所有结点已经打印完毕，可以继续下一层

3、之字形打印二叉树

请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。例如：

3.jpeg

1
3 2
4 5 6 7
15 14 13 12 11 10 9 8

思路：

按之字形顺序打印二叉树需要两个栈，在打印某一层的结点时，把下一层的子结点保存到相应的栈里，如果当前打印的是奇数层（第一层、第三层等），则先保存左子结点再保存右子结点到第一个栈里；如果当前打印的是偶数层（第二层、第四层等），则先保存右子结点再保存左子结点到第二个栈里

算法实现

void Print(BinaryTreeNode *pRoot) {
    if (pRoot == nullptr)
        return;

    stack<BinaryTreeNode *> levels[2];
    int current = 0;
    int next = 1;

    levels[current].push(pRoot);
    while (!levels[0].empty() || !levels[1].empty()) {
        // 获取栈顶元素
        BinaryTreeNode *pNode = levels[current].top();
        levels[current].pop();

        // 打印值
        printf("%d", pNode->m_nValue);

        // 入栈子结点
        if (current == 0) {
            if (pNode->m_pLeft != nullptr) {
                levels[next].push(pNode->m_pLeft);
            }
            if (pNode->m_pRight != nullptr) {
                levels[next].push(pNode->m_pRight);
            }
        } else {
            if (pNode->m_pRight != nullptr) {
                levels[next].push(pNode->m_pRight);
            }
            if (pNode->m_pLeft != nullptr) {
                levels[next].push(pNode->m_pLeft);
            }
        }

        // 当前行结点打印结束
        if (levels[current].empty()) {
            printf("\n"); // 换行
            current = 1 - current; 
            next = 1 - next;
        }
    }
}

参考

《剑指offer》