中序遍历二叉树分为两种方法，第一种是递归法，第二种是迭代法，递归法在LeetCode OJ上被称为是trivial（不重要的），所以重点在迭代法遍历二叉树
- 递归法
struct TreeNode {
int value;
TreeNode *leftTreeNode;
TreeNode *rightTreeNode;
};
void traverseInOrder (TreeNode *treeNode) {
if (treeNode != NULL) {
traverseInOrder(treeNode->leftTreeNode);
std::cout << treeNode->value;
traverseInOrder(treeNode->rightTreeNode);
}
}
- 迭代法
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
};
vector<int> traverseInOrder (TreeNode *root) {
vector<int> allValueInOrder;
TreeNode *currentNode = root;
stack<TreeNode *> stack;
while (currentNode || !stack.empty()) {// isEmpty类型为变量为空返回YES，所以一般判断都应该取反
if (currentNode) {
stack.push(currentNode);
currentNode = currentNode->left;
} else {
currentNode = stack.top();
stack.pop();// pop返回了void，不能直接进行pop返回数据
allValueInOrder.push_back(currentNode->val);
currentNode = currentNode->right;
}
}
return allValueInOrder;
}
