LeetCode 94：Binary Tree Inorder Traversal（中序遍历）

本文主要是介绍LeetCode 94：Binary Tree Inorder Traversal（中序遍历），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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

For example:
Given binary tree {1,#,2,3},

1
\
2
/
3

return [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<int> inorderTraversal(TreeNode* root) {vector<int> result;stack<TreeNodeWrapper*> 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<int> inorderTraversal(TreeNode* root) {vector<int> 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; }
};