先序遍历、中序遍历二叉树非递归实现-蒲公英云

先序遍历、中序遍历二叉树非递归实现

先序遍历

leetcode 144. binary-tree-preorder-traversal

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        return preorderTraversalIteratively(root);
    }
    /* 先序遍历递归版本 */
    void preorderTraversalRecursion(TreeNode* root){
        if(root){
            cout<<root->val<<endl;
            preorderTraversalRecursion(root->left);
            preorderTraversalRecursion(root->right);
        }
    }
    /* 先序遍历非递归版本 */
    vector<int> preorderTraversalIteratively(TreeNode* root){
        stack<TreeNode*>S;  // 初始化栈 S
        vector<int>v;       // v 记录访问节点的顺序
        // 两种情况：
        // 只要左子树不为空那么就一直向左走
        // 走到最左边时，看是否有
        while(root || !S.empty()){
            // 左子树不为空一直往左走
            if(root){
                v.push_back(root->val);  // 访问根节点
                S.push(root); // 根节点入栈，因为左子树访问完毕时需要回来再访问右子树
                root = root->left; // 访问左子树
            }
            // 走到最左边后，开始向右走
            else{
                root = S.top();
                S.pop();
                root = root->right;
            }
        }
        return v;
    }
};

中序遍历

leetcode 94. Binary Tree Inorder Traversal

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        return inorderTraversalInteratively(root);
    }
    /* 中序遍历递归版本*/
    void inorderTraversalRecursion(TreeNode* root){
        if(root){
            inorderTraversalRecursion(root->left);
            cout<<root->val<<endl;  // 访问根节点
            inorderTraversalRecursion(root->right);
        }
    }
    /* 中序遍历非递归版本 */
    vector<int> inorderTraversalInteratively(TreeNode* root){
        stack<TreeNode*>S;
        vector<int>v;
        /* 第一种写法 while(root || !S.empty()){ if(root){ S.push(root); root = root->left; } else{ root = S.top(); v.push_back(root->val); // 注意与先序遍历的区别 S.pop(); root = root->right; } } */
        /* 第二种写法 */
        while(root || !S.empty()){
            /* 左子树全部入栈 */
            while(root){
                S.push(root);
                root = root->left;
            }
            if(!S.empty()){
                root = S.top();
                v.push_back(root->val);  // 访问根节点
                S.pop();
                root = root->right; // 下一次循环遍历右子树
            }
        }
        return v;
    }
};