中序遍历二叉树

序

早上做题，终于靠自己实力做出了多年都没有搞定的题目：非递归中序遍历二叉树。以前碰到这个题想很久想不出来，然后就去网上找一下别人的思路和答案，理解之后记住，然而，过段时间又忘了，下次碰到又得重新来。

这次终于在不查任何资料的情况下做出来了，对刷题又有了信心。

题目

LeetCode题目的中文描述如下：

给定一个二叉树，返回它的中序遍历。

示例:
输入: [1,null,2,3]
  1
   \
    2
   /
  3

输出: [1,3,2]
进阶: 递归算法很简单，你可以通过迭代算法完成吗？

英文描述如下：

Given a binary tree, return the inorder traversal of its nodes’ values.

Example:
Input: [1,null,2,3]
  1
   \
    2
   /
  3

Output: [1,3,2]
Follow up: Recursive solution is trivial, could you do it iteratively?

思路

看到要求非递归遍历，直接就能想到不用递归就得用迭代或栈来代替，而这个地明显就只能用栈¹，确定用栈，剩下就是考虑怎么入栈和出栈，避免重复访问、遗漏等问题了，所以我在栈之外设计两个list保存已访问的元素（判断当前元素是否可以被访问）和正在栈中的元素（避免重复入栈）。

具体代码如下：

/**
 * 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) {
        vector<int> r;
        stack<TreeNode *> s;
        TreeNode * p = root;
        set<TreeNode *> st1; // 已访问的
        set<TreeNode *> st2;  // 已在栈中的

        while (p != NULL) {
            if (st1.count(p->left) > 0) {
                r.push_back(p->val);
                st1.insert(p);
                
                if (!s.empty()) {
                    p = s.top();
                    s.pop();
                    st2.erase(p);
                } else {
                    p = NULL;
                }
                
                continue;
            }
            
            if (p->right != NULL) {
                if (st1.count(p->right) == 0
                   && st2.count(p->right) == 0) {
                    s.push(p->right);
                    st2.insert(p->right);
                }
            }

            if (p->left != NULL) {
                s.push(p);
                s.push(p->left);
            } else {
                r.push_back(p->val);
                st1.insert(p);
            }
            if (!s.empty()) {
                p = s.top();
                s.pop();
                st2.erase(p);
            } else {
                p = NULL;
            }
        }
        return r;
    }
};

结果

最后也是一次AC，自己的基本功还是可以。

总结

看来刷题确实有助于提升思维，这个可以继续坚持下去。

Footnotes

¹ 比如二分查找，如果不用递归，就需要用迭代来完成。