Algorithm

OJ address

OJ website : 从上往下打印二叉树

Description

从上往下打印出二叉树的每个节点，同层节点从左至右打印。

Solution in C++

//从上往下打印出二叉树的每个节点，同层节点从左至右打印。

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

struct TreeNode {
    char val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};

int pos;
char TreeStr[100];

class Solution {
public:
    TreeNode* InsertNode() {
        char ch = TreeStr[pos++];
        if (ch == '0') {
            return NULL;
        }
        else {
            TreeNode *newNode = new TreeNode(ch);
            newNode->left = InsertNode();
            newNode->right = InsertNode();
            return newNode; 
        }
        return NULL; 
    }

    void PreOrder(TreeNode *root) {
        if (root) {
            cout << root->val;
            PreOrder(root->left);
            PreOrder(root->right);
        }
    }

    vector<char> PrintFromTopToBottom(TreeNode* root) {
        int rear, front;
        rear = front = 0;
        std::vector<char> v;
        if (root) TreeArray[rear++] = root;
        while(rear != front) {
            if (TreeArray[front]) {
                v.push_back(TreeArray[front]->val);
                TreeArray[rear++] = TreeArray[front]->left;
                TreeArray[rear++] = TreeArray[front]->right;
            }
            ++front;
        }
        return v;
    }

private:
    TreeNode* TreeArray[100];
};

int main(int argc, char const *argv[])
{
    Solution solution;
    pos = 0;
    cin >> TreeStr;
    TreeNode *root = solution.InsertNode();
    std::vector<char> vec = solution.PrintFromTopToBottom(root);

    for(vector<char>::iterator it=vec.begin();it!=vec.end();it++)
        cout<<*it<<endl;

    return 0;
}

My Idea

用一个队列保存被访问的当前节点的左右孩子以实现层序遍历。