preOrder, inOrder, postOrder 的recursion和iteration实现 类型

这三种用通用iteration模板解决，好记住。
执行push_back进数组的位置不同。

inOrder（左根右）用的场景最多。

Code(Language:C++) (Judger:ip-172-31-12-4)

/**
 * Definition of TreeNode:
 * class TreeNode {
 * public:
 *     int val;
 *     TreeNode *left, *right;
 *     TreeNode(int val) {
 *         this->val = val;
 *         this->left = this->right = NULL;
 *     }
 * }
 */

class Solution {
public:
    /**
     * @param root: A Tree
     * @return: Inorder in ArrayList which contains node values.
     */
    vector<int> inorderTraversal(TreeNode * root) {
        // write your code here
        vector<int> res; 
        if(root == NULL){
            return res; 
        }
        TreeNode *p = root; 
        std::stack<TreeNode *> stk;
        while(!stk.empty() || p != NULL){
            while(p != NULL){
                stk.push(p);
                p = p->left; 
            }
            TreeNode *tmp = stk.top();
            stk.pop();
            res.push_back(tmp->val); 
            p = tmp->right; 
        }
        return res; 
    }
};preOrder 根左右class Solution {
public:
    /**
     * @param root: A Tree
     * @return: Preorder in ArrayList which contains node values.
     */
    vector<int> preorderTraversal(TreeNode * root) {
        // write your code here
        // stack 
        // 根左右
        // 用通用模板
        vector<int> res; 
        if(root == NULL){
            return res; 
        }
        stack<TreeNode *> stk; 
        TreeNode *p = root; 
        while(!stk.empty() || p != NULL){
            while(p != NULL){
                stk.push(p);
                res.push_back(p->val); 
                p = p->left; 
            }
            TreeNode *temp = stk.top();
            stk.pop();
            p = temp->right;
        }
        return res; 
    }
};




Code(Language:C++) (Judger:ip-172-31-21-252)









/**
 * Definition of TreeNode:
 * class TreeNode {
 * public:
 *     int val;
 *     TreeNode *left, *right;
 *     TreeNode(int val) {
 *         this->val = val;
 *         this->left = this->right = NULL;
 *     }
 * }
 */

class Solution {
public:
    /**
     * @param root: A Tree
     * @return: Preorder in ArrayList which contains node values.
     */
    vector<int> preorderTraversal(TreeNode * root) {
        // write your code here
        //根左右 not 通用模板
        vector<int> res;
        if(root == NULL){
            return res; 
        }
        std::stack<TreeNode *> stk;
        stk.push(root); 
        while(!stk.empty()){
            TreeNode *tmp = stk.top();
            stk.pop(); 
            res.push_back(tmp->val); 
            if(tmp->right){
                stk.push(tmp->right); 
            }
            if(tmp->left){
                stk.push(tmp->left); 
            }
        }
        return res; 
    }
};


postOrder 




Code(Language:C++) (Judger:ip-172-31-5-19)









/**
 * Definition of TreeNode:
 * class TreeNode {
 * public:
 *     int val;
 *     TreeNode *left, *right;
 *     TreeNode(int val) {
 *         this->val = val;
 *         this->left = this->right = NULL;
 *     }
 * }
 */

class Solution {
public:
    /**
     * @param root: A Tree
     * @return: Postorder in ArrayList which contains node values.
     */
    vector<int> postorderTraversal(TreeNode * root) {
        // write your code here
        //左右根
        
        // preorder: 根左右
        // Postorder: 左右根，可由根右左，变过来
        vector<int> res; 
        if(root == NULL){
            return res; 
        }
        stack<TreeNode *> stk; 
        TreeNode *p = root; 
        while(!stk.empty() || p != NULL){
            while(p != NULL){
                stk.push(p);
                res.insert(res.begin(), p->val); 
                p = p->right; //这里是right
            }
            TreeNode *temp = stk.top();
            stk.pop();
            p = temp->left; //这里是left
        }
        return res; 
    }
};