二叉树的遍历

        二叉树遍历包括先序、中序、后序和层次遍历。先序、中序和后序属于深度优先，层次遍历属于宽度优先。

        前者可以通过递归和迭代方式遍历，迭代方式借助栈。层次遍历则可以借助队列。

具体：

测试用例：

int main(int argc, char* argv[]) {
    std::cout << "hello binary tree \n";
    
    // create  tree 1
    TreeNode* root = new TreeNode(1);
    root->leftChild = new TreeNode(2);
    root->rightChild = new TreeNode(3);
    root->leftChild->leftChild = new TreeNode(4);
    root->leftChild->rightChild = new TreeNode(5);
    root->rightChild->leftChild = new TreeNode(6);
    root->rightChild->rightChild = new TreeNode(7);


    auto result = levelTraversal(root);
    std::cout << "level traversal : \n";
    for (int elem : result) {
        std::cout << elem << " ";
    }
    std::cout << std::endl;

    std::cout << "preorder traversal recursive  : \n";
    std::vector<int> result1;
    preOrderTraversalRecursive(root, result1);
    for (int elem : result1) {
        std::cout << elem << " ";
    }
    std::cout << std::endl;

    std::cout << "preorder traversal iterative: \n";
    std::vector<int> result11 = preOrderTranversalIterative (root);
    for (int elem : result11) {
        std::cout << elem << " ";
    }
    std::cout << std::endl;

    std::cout << "inorder traversal recursive  : \n";
    std::vector<int> result2;
    inOrderTraversalRecursive(root, result2);
    for (int elem : result2) {
        std::cout << elem << " ";
    }
    std::cout << std::endl;

    std::cout << "inorder traversal iterative: \n";
    std::vector<int> result22 = inOrderTranversalIterative(root);
    for (int elem : result22) {
        std::cout << elem << " ";
    }
    std::cout << std::endl;

    std::cout << "postorder traversal recursive  : \n";
    std::vector<int> result3;
    postOrderTraversalRecursive(root, result3);
    for (int elem : result3) {
        std::cout << elem << " ";
    }
    std::cout << std::endl;

    std::cout << "postorder traversal iterative: \n";
    std::vector<int> result33 = postOrderTranversalIterative(root);
    for (int elem : result33) {
        std::cout << elem << " ";
    }
    std::cout << std::endl;

    // destroy tree 1
    delete root->rightChild->leftChild;
    delete root->rightChild->rightChild;
    delete root->leftChild->leftChild;
    delete root->leftChild->rightChild;
    delete root->leftChild;
    delete root->rightChild;
    delete root;


   

遍历方法

include <iostream>
#include <vector>
#include <queue>
#include <stack>

/**
 * 接口声明
 */

struct TreeNode {
    int val;
    struct TreeNode* leftChild;
    struct TreeNode* rightChild;
    TreeNode(int n): val(n), leftChild(nullptr), rightChild(nullptr) {}
    TreeNode(int n, TreeNode* l, TreeNode* r): val(n), leftChild(l), rightChild(r) {} 
};

/**
 * 递归方式
 */
// 先序遍历
void preOrderTraversalRecursive(TreeNode* bt, std::vector<int>& result);
// 中序遍历
void inOrderTraversalRecursive(TreeNode* bt, std::vector<int>& result);
//
// 后序遍历
void postOrderTraversalRecursive(TreeNode* bt, std::vector<int>& result);

/**
 * 迭代方式
 */
// 先序遍历
std::vector<int> preOrderTranversalIterative(TreeNode* bt);
//
// 中序遍历
std::vector<int> inOrderTranversalIterative(TreeNode* bt);
//
// 后序遍历
std::vector<int> postOrderTranversalIterative(TreeNode* bt);


/**
 * 层次遍历
 */
std::vector<int> levelTraversal(TreeNode* bt);

/***********************************************************************************************************/
/* 实现  */
/**********************************************************************************************************/

void preOrderTraversalRecursive (TreeNode* bt, std::vector<int>& result) {
    if (!bt) return;
    result.push_back(bt->val);
    preOrderTraversalRecursive(bt->leftChild, result);
    preOrderTraversalRecursive(bt->rightChild, result);
}

void inOrderTraversalRecursive (TreeNode* bt, std::vector<int>& result) {
    if (!bt) return;
    inOrderTraversalRecursive(bt->leftChild, result);
    result.push_back(bt->val);
    inOrderTraversalRecursive(bt->rightChild, result);
}

void postOrderTraversalRecursive (TreeNode* bt, std::vector<int>& result) {
    if (!bt) return;
    postOrderTraversalRecursive(bt->leftChild, result);
    postOrderTraversalRecursive(bt->rightChild, result);
    result.push_back(bt->val);
}

std::vector<int> preOrderTranversalIterative(TreeNode* bt) {
    std::vector<int> result;
    if (!bt) return result;

    std::stack<TreeNode*> s;
    auto root = bt;
    while (root || !s.empty()) {
        while (root) {
            result.push_back(root->val); // 遍历点！
            s.push(root);
            root = root->leftChild;
        }

        root = s.top();
        s.pop();
        root = root->rightChild;
    }

    return result;   
}

std::vector<int> inOrderTranversalIterative(TreeNode* bt) {
    std::vector<int> result;
    if (!bt) return result;

    std::stack<TreeNode*> s;
    auto root = bt;
    while (root || !s.empty()) {
        while (root) {
            s.push(root);
            root = root->leftChild;
        }

        root = s.top();
        s.pop();
        result.push_back(root->val);
        root = root->rightChild;
    }

    return result;
}

std::vector<int> postOrderTranversalIterative(TreeNode* bt) {
    std::vector<int> result;
    if (!bt) return result;
    
    std::stack<TreeNode*> s;
    auto root = bt;
    TreeNode* prev = nullptr;
    while (root || !s.empty()) {
        while (root) {
            s.push(root);
            root = root->leftChild;
        }
        
        root = s.top();
        if (root->rightChild == nullptr || root->rightChild == prev) {
            result.push_back(root->val);
            prev = root;
            s.pop();
            root = nullptr;
        } else {
            root = root->rightChild;
        }
    }

    return result; 
}


std::vector<int> levelTraversal(TreeNode* bt) {
    std::vector<int> result;
    if (bt == nullptr) return result;

    auto ptr = bt;
    std::queue<TreeNode*> q;
    q.push(ptr);
    while(!q.empty()) {
        auto t = q.front();
        q.pop();
        result.push_back(t->val);
        if (t->leftChild) q.push(t->leftChild);
        if (t->rightChild) q.push(t->rightChild);
    }
    return result;
}