树的三种非递归遍历方式

这是面试之前准备的时候写的，为了是让自己回忆一下，以后记不得了也好做个参照，所以不做详述了。

非递归的本质是模拟递归

代码通过了LeetCode的测试

非递归先序

先序非递归的思路是:

用栈保存左子树

1、遍历指针从根开始；

2、每遇到一个节点，只要不空，就访问它，并把它入栈；遍历指针指向左子树，为空则退出循环；

3、如果栈不为空，那么找栈顶元素的右子树入栈，再进行循环。

模拟的就是先根，再左子树，再右子树的过程。

vector<int> preorderTraversal(TreeNode* root) {
        vector<int> res;
        stack<TreeNode *> stk;
        TreeNode *curr = root;
        
        while (curr || !stk.empty()) {
            while (curr) {
                res.push_back(curr->val);
                stk.push(curr);
                curr = curr->left;
            }
            
            if (!stk.empty()) {
                curr = stk.top();
                stk.pop();
                curr = curr->right;
            }
        }
        
        return res;
}

还有一种思路是先右子树入栈，再左子树入栈，是挺直接的思路，在这里就不写了。

非递归中序

中序遍历和先序遍历的区别仅仅在于什么时候访问元素

1、遍历指针从根开始；

2、每遇到一个节点，只要不空，就把它入栈；遍历指针指向左子树，为空则退出循环；

3、如果栈不为空，首先访问栈顶元素，然后栈顶元素的右子树入栈，再进行循环。

vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        stack<TreeNode *> stk;
        TreeNode *curr = root;
        
        while (curr || !stk.empty()) {
            while (curr) {
                stk.push(curr);
                curr = curr->left;
            }
            
            if (!stk.empty()) {
                curr = stk.top();
                res.push_back(curr->val);
                stk.pop();
                curr = curr->right;
            }
        }
        
        return res;
}

非递归后序1

第一种思路是双栈的思路

后序遍历的顺序是左孩子—>右孩子—>根节点。如果用栈的思路应该是按照根节点—>右孩子—>左孩子的顺序入栈。先序遍历的顺序是根节点—>左孩子—>右孩子，但是由于它不是先访问根，所以需要按照根节点—>右孩子—>左孩子的顺序记录所有入栈的节点后一起访问。

vector<int> postorderTraversal(TreeNode* root) {
        vector<int> res;
        stack<TreeNode *> stk1;
        stack<TreeNode *> stk2;
        TreeNode *curr = root;
        
        while (curr || !stk1.empty()) {
            while (curr) {
                stk1.push(curr);
                stk2.push(curr);
                curr = curr->right;
            }
            
            if (!stk1.empty()) {
                curr = stk1.top();
                stk1.pop();
                curr = curr->left;
            }
        }
        
        while (!stk2.empty()) {
            curr = stk2.top();
            stk2.pop();
            res.push_back(curr->val);
        }
        
        return res;
}

但是上述思路多用了一个栈，耗空间更多，且又需要一次整体遍历stk2，费时费力，用下面一种方法可以解决它。

非递归后序2

要访问一个节点的条件是上一个被访问的节点是它的右孩子，这点很难直接处理，所以可以增加一个变量prev来判断当前节点curr的上一个节点是否是双亲和孩子。

同样用栈记录访问的顺序，先右孩子入栈后左孩子。

1、若curr的左右孩子为空，或者若curr是prev的父亲，则访问；

2、不是这两种情况的话就将curr的孩子入栈，先右孩子再左孩子(如果存在的话)，这样右孩子和左孩子都存在时会先访问左孩子，再右。

vector<int> postorderTraversal(TreeNode* root) {
        vector<int> res;
        if (root == NULL)
            return res;
        stack<TreeNode *> stk;
        TreeNode *curr = root, *prev = NULL;
        stk.push(root);
        
        while (!stk.empty()) {
            curr = stk.top();
            
            if((curr->left == NULL && curr->right == NULL) || 
               (prev != NULL && (curr->left==prev || curr->right==prev))) {  
                res.push_back(curr->val); 
                stk.pop(); 
                prev = curr;  
            }  
            else {    
                if(curr->right)  
                    stk.push(curr->right);  
                if(curr->left)  
                    stk.push(curr->left); 
            } 
        }
        
        return res;
}