本文共 2232 字，大约阅读时间需要 7 分钟。
Given a binary tree, return the inorder traversal of its nodes’ values.
For example:
Given binary tree {1,#,2,3},1
\ 2 / 3return [1,3,2].
题目要求对二叉树进行非递归的中序遍历，所谓中序遍历即，先访问左子树、再访问根节点、然后是右子树。通常采用递归的方法，题目要求采用非递归的方法实现。算法如下：1）如果根节点非空，将根节点加入到栈中。
2）如果栈不空，取栈顶元素（暂时不弹出），
如果左子树已访问过，或者左子树为空，则弹出栈顶节点，将其值加入数组，如有右子树，将右子节点加入栈中。 如果左子树不为空，切未访问过，则将左子节点加入栈中，并标左子树已访问过。
3）重复第二步，直到栈空。
代码如下：
//包裹结构体，标明左子树是否已经访问过 struct TreeNodeWrapper{ struct TreeNode *pNode; bool lVisited; //左子树已访问过 bool rVisited; //右子树已访问过 TreeNodeWrapper(TreeNode * p){pNode = p; lVisited= false; rVisited= false;}};class Solution {public: vector inorderTraversal(TreeNode* root) { vector result; stack node_stack; if (root == NULL) return result; node_stack.push(new TreeNodeWrapper(root)); while(!node_stack.empty()){ TreeNodeWrapper* pNode = node_stack.top(); if (pNode->lVisited || pNode->pNode->left==NULL) //左子树已访问过，或者为空 { node_stack.pop(); result.push_back(pNode->pNode->val); //访问节点，访问右子树 if (pNode->pNode->right) { node_stack.push(new TreeNodeWrapper(pNode->pNode->right)); } delete pNode; }else{ //访问左子树，并标记 node_stack.push(new TreeNodeWrapper(pNode->pNode->left)); pNode->lVisited = true; } } return result; }}; 方法二，不使用包裹结构体。上面的解法虽然原理上比较简单，当使用了一个包裹结构体，和大量的New/delete操作，显得比较复杂。不如下面这种算法比较简洁。
class Solution {public: vector inorderTraversal(TreeNode* root) { vector result; stack< TreeNode *> node_stack; TreeNode * pNode = root; while (pNode || !node_stack.empty()) { //节点不为空，加入栈中，并访问节点左子树 if (pNode != NULL) { node_stack.push(pNode); pNode = pNode->left; }else{ //节点为空，从栈中弹出一个节点，访问这个节点， pNode = node_stack.top(); node_stack.pop(); //访问节点右子树 result.push_back(pNode->val); pNode = pNode->right; } } return result; }}; 转载地址：http://wbxti.baihongyu.com/