二叉树的中序遍历（leetcode-94）

题目

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

思路

递归很简单，这里要求非递归，其实也不难（由于没写过写了好久= =）。

大致思路就是，左儿子不空就一直走左儿子，空了就走右儿子。然后重复上述。很显然，递归转非递归肯定是要用到栈的（因为要回溯，后遍历的节点是先输出的）。

这里有些实现细节：

• 用一个指针一直指向当前遍历的节点
• 里面要有一个小循环一直走左儿子，外面的大循环利用栈来回溯

具体可以看代码，一目了然

我一开始还想用两个指针，一个指向父节点，一个指向当前节点。后来发现父节点就是栈顶的元素= =

代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
#include <vector>
#include <iostream>
using namespace std;
class Solution {
public:
	// 非递归求解
	vector<int> inorderTraversal(TreeNode* root) {
		// init
		stack<TreeNode*> sta;
		vector<int> ans;

		 while (root != nullptr || !sta.empty()){
        	// 如果有左儿子就压栈
			while (root != nullptr) {
				sta.push(root);
				root = root->left;
			}

			// 没有就该输出
			root = sta.top();
			sta.pop();
			ans.push_back(root->val);
			// 然后看看有无右儿子
			root = root->right;
		}
        return ans;
	}
};

二叉树的中序遍历（leetcode-94）

原文：https://www.cnblogs.com/destinyzk/p/13906875.html