LeetCode 二叉树的中序遍历（递归和非递归算法）

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

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

进阶: 递归算法很简单，你可以通过迭代算法完成吗？
思路分析：二叉树的遍历有先序遍历、中序遍历、后序遍历、层次遍历。
先序遍历：先访问根节点，然后访问左子树，再访问右子树。
中序遍历：先访问左子树，然后访问根节点，再访问右子树。
后序遍历：先访问左子树，然后访问右子树，再访问根节点。
层次遍历：从数的根部按照深度从小到大访问每一层，每层访问从左至右。
方法一：递归算法实现。此法比较好理解。

/**
 * 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> result;
	void myInorderTraversal(TreeNode* root) {
		if (root == NULL) {
			return;
		}
		//先遍历左子树
		if (root->left != NULL) {
			myInorderTraversal(root->left);
		}
		//遍历当前根节点
		result.push_back(root->val);
		//再遍历右子树
		if (root->right != NULL) {
			myInorderTraversal(root->right);
		}
	}
	vector<int> inorderTraversal(TreeNode* root) {
		myInorderTraversal(root);//中序遍历
		return result;
	}
};

方法二：非递归算法。借助栈的辅助进行访问。

/**
 * 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> result;
	vector<int> inorderTraversal(TreeNode* root) {
		stack<TreeNode*> myStack;//辅助栈，由于保护现场
		while (!myStack.empty() || root != NULL) {
			if (root != NULL && root->left != NULL) {//如果左子树不为空
				myStack.push(root);//保护现场
				root = root->left;//先访问左子树
				continue;
			}
			if (root == NULL) {
				if (!myStack.empty()) {
					root = myStack.top();//恢复现场
					myStack.pop();
				}
				else {
					break;
				}
			}
			result.push_back(root->val);//访问当前跟节点
			root = root->right;//访问右子树
		}
		return result;
	}
};