中序遍历二叉树

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

示例:

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

输出: [1,3,2]

进阶: 递归算法很简单，你可以通过迭代算法完成吗？

参考https://www.cnblogs.com/grandyang/p/4297300.html的答案

一般对于树的遍历，有两种解法：递归和非递归 。对于递归：对于左子树调用递归函数，根节点访问值，右节点调用递归函数 对于非递归：1.使用栈 2.不使用栈 

1.递归

/**
 * 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> res;
        inorder(root,res);
        return res;
    }
    void inorder(TreeNode *root,vector<int> &res){
        if(!root) return;
        if(root->left) inorder(root->left,res);
        res.push_back(root->val);
        if(root->right) inorder(root->right,res);
    }
};

2.非递归

2.1非递归（使用栈）

基本思想：从根节点开始，把根节点压入栈，然后再将其所有左子节点压入栈，然后取出栈顶元素，保存节点值，然后把当前节点移动到其右子节点上，若存在右子节点，则下次循环又可将其左子节点压入栈中

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        stack<TreeNode *> s;
        TreeNode *p=root;
        while(p||!s.empty()){
            while(p){
                s.push(p);
                p=p->left;
            }
            p=s.top();
            s.pop();
            res.push_back(p->val);
            p=p->right;
        }
        return res;
    }
};

2.2非递归（不使用栈）

    由于不使用栈，所以它的空间复杂度是常量。这种非递归不使用栈的方法，有个专门的名字，叫螺纹二叉树。这种树把所有为空的左子节点指向中序遍历之前的节点，把所有为空的右子节点指向中序遍历之后的节点。

1. 初始化指针cur指向root

2. 当cur不为空时

　 - 如果cur没有左子结点

　     a) 打印出cur的值

　　  b) 将cur指针指向其右子节点

　 - 反之

　    将pre指针指向cur的左子树中的最右子节点　

　　　  * 若pre不存在右子节点

　　　       a) 将其右子节点指回cur

　　　　    b) cur指向其左子节点

　　　  * 反之

　　　　　 a) 将pre的右子节点置空

　　　　　 b) 打印cur的值

　　　　　 c) 将cur指针指向其右子节点