二叉树的遍历递归非递归

#include 
#include 
using namespace std;

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

// 先序遍历，递归
// [1] [2] [4] [5] [6] [7] [3]
void preorder1(TreeNode* root) {
    if(!root)   return;
    cout <<‘[‘ <val <<"] ";
    preorder1(root->left);
    preorder1(root->right);
}

// 中序遍历，递归
// [4] [2] [6] [5] [7] [1] [3]
void inorder1(TreeNode* root) {
    if(!root)   return;
    inorder1(root->left);
    cout <<‘[‘ <val <<"] ";
    inorder1(root->right);
}

// 后序遍历，递归
// [4] [6] [7] [5] [2] [3] [1]
void postorder1(TreeNode* root) {
    if(!root)   return;
    postorder1(root->left);
    postorder1(root->right);
    cout <<‘[‘ <val <<"] ";
}

// 先序遍历，非递归
void preorder2(TreeNode* root) {
    if(!root)   return;
    stack s;
    s.push(root);
    while(!s.empty()) {
        TreeNode* node = s.top();
        cout <<‘[‘ <val <<"] ";
        s.pop();
        if(node->right)  s.push(node->right);
        if(node->left)  s.push(node->left);
    }
}

// 先序遍历，非递归
void preorder3(TreeNode* root) {
   stack s;
    while(root != NULL || !s.empty()) {
        if(root != NULL) {
            s.push(root);
            cout <<‘[‘ <val <<"] ";
            root = root->left;
        }
        else {
            root = s.top();
            s.pop();
            root = root->right;
        }
    }
}