非递归遍历二叉树

前言

二叉树用递归实现前中后序遍历虽然思路简单，但是由于OS分配给一个进程的栈空间很小，一般是8MB，在VS中，即便是release版本下，效率差别也不是很大。所以递归转非递归的原因不在于效率，而是递归有栈溢出的风险。

而进程被分配的堆空间大小能有几个G，所以在堆上模拟递归的过程能让递归的“层数”更深。通常使用循环和栈模拟递归，例如斐波那契数列可以用循环模拟递归，快排可以用栈模拟。

非递归模拟递归，最重要的是模拟递归的过程。

1. 二叉树的前序遍历

前序遍历的规则：根结点、左子树、右子树。这对每一个子树都是一样的，所以就整棵树而言，前序遍历最先访问的就是左路节点，接着就是左路节点的右子树。下面同样用cur表示当前遍历的结点。

想象递归的过程：每层栈帧都会保存cur的地址，当cur走到nullptr时，就会层层往上返回。那么我们可以用一个栈模拟栈帧存储cur的地址和返回的过程。

1. 将左路结点全部入栈，入栈的同时访问结点的值，当cur遇到nullptr，即入栈完毕;
2. 取栈顶结点top，即左路最深未被处理的结点，pop。对它的右子树重复步骤1p；
3. 只要栈或cur至少有一个不为空，则说明还未遍历完毕，继续重复以上操作。

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        TreeNode* cur = root;
        vector<int> ret;
        stack<TreeNode*> st;

        while(!st.empty() || cur)
        {
            while(cur)
            {
                st.push(cur);
                ret.push_back(cur->val);
                cur = cur->left;
            }

            TreeNode* top = st.top();
            st.pop();

            cur = top->right;
        }

        return ret;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

精华在循环中的最后一句代码：cur = top->right;，它让cur的位置从左子树变成了右子树，然后重复之前的步骤。

一个结点出栈，说明这个节点及它的左子树访问完了，就剩右子树。

2. 二叉树的中序遍历

中序遍历的思路也是类似的，不同之处是中序遍历的规则是左子树、根结点、右子树，访问根结点的时机是走完左子树之后，所以是在取出栈顶结点的同时访问根结点的值。

步骤如下：

1. 将左路所有结点入栈；
2. 取出栈顶结点top的同时访问结点的值，pop。对它的右子树重复步骤1。
3. 只要栈或cur至少有一个不为空，则说明还未遍历完毕，继续重复以上操作。

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        TreeNode* cur = root;
        vector<int> ret;
        stack<TreeNode*> st;

        while(!st.empty() || cur)
        {
            while(cur)
            {
                st.push(cur);
                cur = cur->left;
            }

            TreeNode* top = st.top();
            st.pop();
            ret.push_back(top->val);

            cur = top->right;
        }

        return ret;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

3. 二叉树的后序遍历

后序遍历的思路稍有不同，因为后序遍历的规则是先访问完左右子树然后再访问根结点。什么时候能访问结点：

• 左右子树都为空，也就是结点没有孩子；
• 左右子树都访问过；

其实可以不用判断左子树， 因为左子树已经被入栈了，只要看右子树的情况即可。如何判断右子树是否被访问过？

• 用prev保存栈顶结点，那么对于top而言，prev就是上次访问的结点，当top->right==prev时，表示上一次访问的节点是右子树的根结点，这时候就说明cur的右子树已经被访问过了。

区分：一个结点的右子树不为空的情况下：

1. 如果右子树没有访问，应该要访问右子树；
2. 右子树访问过了，就要访问根结点。

步骤：

1. 将左路所有结点入栈；
2. 取栈顶结点top：
   • 如果top的右子树已经被访问过了，访问top的值，pop。更新prev为top；
   • 如果top的右子树没有被访问，对它的右子树重复步骤1、2。

通过图示理解prev的作用：

class Solution {
public:
	vector<int> postorderTraversal(TreeNode* root) {
		stack<TreeNode*> st; 
		vector<int> ret;
		TreeNode* cur = root;
		TreeNode* prev = nullptr; // 记录上一次访问的结点
		while (cur || !st.empty())
		{
			//1. 将左路结点入栈
			while (cur)
			{
				st.push(cur);
				cur = cur->left;
			}
			//2. 取出栈顶结点
			TreeNode* top = st.top();
			//3. 结点的右子树为空，或右子树已经访问过，则访问该结点
			if (top->right == nullptr || top->right == prev)
			{
				// 访问后弹出
				st.pop();
				ret.push_back(top->val);
				// 更新上一次访问的结点
				prev = top;
			}
			else //4. 若取出结点的右子树还未被访问，访问右子树
			{
				cur = top->right;
			}
		}
		return ret; 
	}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34