Leetcode—中序遍历二叉树

中序遍历二叉树

【题目描述】

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

示例 :
输入: [1, null, 2, 3]
1

2
/
3

输出: [1, 3, 2] (官方题解)

【解题思路】

1： 经典的递归方法， 只需编写一个递归函数，然后内部按照 左— 根— 右 遍历并调用自身实现递归

2：基于栈的非递归算法，从根节点开始, 只要 当前节点存在 或 栈不为空，则重复下面操作

• 如果当前结点存在，则进栈并遍历左子树 。
• 否则退栈并访问，并遍历右子树 。

【样例代码】

//// 为便于理解, 直接递归了。
class Solution 
{
public:
	vector <int> res;
	void Traversal(TreeNode *root)
	{
		if (root != NULL)
		{
			Traversal(root->left);
			res.push_back(root->val);
			Traversal(root->right);
		}
	}
	vector<int> inorderTraversal(TreeNode* root) 
	{
		Traversal(root);
		return res;
	}
};