每日一题-08-二叉树中序遍历二叉树中序遍历给出某二叉树的根节点root，并返回其中序遍历。
示例 1：
输入： root=[1，null，2，3 ]输出： [ 1，3，2 ]示例2 :
输入：根[]输出： []示例3 :
输入： root=[1]输出： [1] 示例 4：
输入： root=[ 1，2 ]输出： [ 2，1 ] http://www.Sina.com /
输入： root=[1，null，2]输出： [ 1，2 ] http://www.Sina.com /
树中的节点数在范围[ 0，100 ]内(-100=Node.val=100来源：吸引(LeetCode ) ) ) ) ) ) ) ) ) )。
链接： https://leet code-cn.com/problems/binary-tree-in order-traversal
版权归互联网所有。 商业转载请联系官方许可证。 非商业转载请注明出处。
1 .直接使用递归遍历(是根据自己以前在《大话数据结构》中学到的方法直接写的) )。
/* * definitionforabinarytreenode.* struct treenode { * intval； * TreeNode *left； * TreeNode *right； *treenode(3360val )0)、left (nullptr )、right (nullptr ) * treenode (intx ) 3360val )、left (nullptr ) ) ) )。 TreeNode *left、treenode*right(:val ) x )、left )、right ) {}*； */class解决方案{ public : vectorintinordertraversal (treenode * root ) { vectorint v； 中间(根，v )； 返回v； }voidmidevery(treenode*node，vectorint vec ) if ) node==nullptr ) { return； } midevery (节点左，vec )； vec.push _ back (节点- val； 中间(节点光，vec )； }； 2 .迭代方法的实现，与第一种方法的时间和空间复杂度一样，利用中序遍历的顺序，利用堆栈来实现树的遍历。
/* * definitionforabinarytreenode.* struct treenode { * intval； * TreeNode *left； * TreeNode *right； *treenode(3360val )0)、left (nullptr )、right (nullptr ) * treenode (intx ) 3360val )、left (nullptr ) ) ) )。 TreeNode *left、treenode*right(:val ) x )、left )、right ) {}*； */class解决方案{ public : vectorintinordertraversal (treenode * root ) { stackTreeNode* st； 矢量输入RES； wile (路线！=nullptr ||！ st.empty () (while ) )路由！=nullptr () ST.push ) ) root； 根=根-左}根=ST.top (； st.pop (； RES.push _ back (根val； 根=根-光}返回RES； }；