二叉树的遍历

先序
递归：

void preorderTraversal(TreeNode* root) {
    if (p !=NULL) {
        cout << p->val << endl;
        preorderTraversal(p->left);
        preorderTraversal(p->right);
    }
}

非递归：

void preorderTraversal(TreeNode* root) {
    stack<TreeNode*> tmp;
    /* p，正在访问的结点 
    TreeNode *p;
    p = root;        
   if (p != nullptr) nodes.push(p);  
        while (!nodes.empty()) {
            p = nodes.top(); nodes.pop();
           cout << p->val<< endl;
            if (p->right != nullptr) nodes.push(p->right);
            if (p->left != nullptr) nodes.push(p->left);
        }
}

中序
递归：

void inorderTraversal(TreeNode* root) {
    if (p !=NULL) {
        inorderTraversal(p->left);
        cout << p->val << endl;
        inorderTraversal(p->right);
    }
}

非递归：

void inorderTraversal(TreeNode* root) {
    stack<TreeNode*> tmp;
    TreeNode *p;
    p = root;
        
    while (!tmp.empty() || nullptr != p) {
        if (nullptr != p) {
            tmp.push(p);
            p = p->left;
        } else {
            p = tmp.top();
            tmp.pop();
            cout << p->val << endl;
            p = p->right;
        }
    }

}

后序
递归：

void postorderTraversal(TreeNode* root) {
    if (p !=NULL) {
        postorderTraversal(p->left);
        postorderTraversal(p->right);
        cout << p->val << endl;
    }
}

非递归

void postorderTraversal(TreeNode* root) {
    stack<TreeNode*> tmp;
    /* p，正在访问的结点，q，刚刚访问过的结点*/
    TreeNode *p, *q;
    p = root;
        
    do {
        while (nullptr != p) {
            tmp.push(p);
            p = p->left;
        }
            
        q = nullptr;
            
        while(!tmp.empty()) {
            p = tmp.top();
            tmp.pop();
            if (p->right == q) {            //重点是这三行代码
                cout << p->val << endl;
                q = p;
            } else {
                tmp.push(p);
                p = p->right;
                break;
            }
        }
            
    } while (!tmp.empty());
}

层次遍历

void largestValues(TreeNode* root) {
    if (root==nullptr)
        return;
    deque<TreeNode*> que;
    que.push_back(root);
 
    while(!que.empty()) {
        TreeNode* node = que.front();
        que.pop_front();
        cout << node->val << endl;

        if (node->left) {
            que.push_back(node->left);
        }
        
        if (node->right) {
            que.push_back(node->right);
        }
    }

}