1.问题描述
非递归中序遍历二叉树。
示例 1：
中序序列：2 1。
示例 2：
中序序列：1 2。
示例 3：
中序序列：2 1 3。
2.难度等级
medium。
3.热门指数
★★★★☆
出题公司：腾讯、B站。
4.解题思路
中序遍历按照“左子树 > 根结点——右子树”的顺序进行访问。而在访问左子树或右子树的时候我们按照同样的方式遍历，直到遍历完整棵树。
因此整个遍历过程天然具有递归的性质，我们可以直接用递归函数来模拟这一过程。
代码语言：javascript复制/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func inorderTraversal(root *TreeNode) []int {
if root == nil {
return nil
}
var nodes []int
lefts := inorderTraversal(root.Left)
nodes = append(nodes, lefts...)
nodes = append(nodes, root.Val)
rights := inorderTraversal(root.Right)
nodes = append(nodes, rights...)
return nodes
}递归很简单，如何使用非递归的方式中序遍历呢？
只要是递归，便可以使用栈模拟递归的过程。
首先遍历根节点，如果非空则入栈。
然后判断栈顶结点是否有左结点，如果有则将左结点入栈。如果没有则出栈，访问该结点，并将其右孩子入栈（如果有的话）。
重复上面一步，直至栈空，完成中序遍历。
复杂度分析：
时间复杂度：O(n)，其中 n 为二叉树结点的个数。二叉树的遍历中每个结点会被访问一次且只会被访问一次。
空间复杂度：O(n)。空间复杂度取决于递归的栈深度，而栈深度在二叉树为一条链的情况下会达到 O(n) 的级别。
5.实现示例
5.1 C
代码语言：javascript复制/**
* 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) {}
* };
*/
// inorderTraversal 非递归中序遍历二叉树。
vector<int> inorderTraversal(TreeNode *root) {
vector<int> res;
stack<TreeNode *> stk;
while (root != nullptr || !stk.empty()) {
while (root != nullptr) {
stk.push(root);
root = root->left;
}
root = stk.top();
stk.pop();
res.push_back(root->val);
root = root->right;
}
return res;
}
5.2 Golang
代码语言：javascript复制/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
// inorderTraversal 非递归中序遍历二叉树。
func inorderTraversal(root *TreeNode) []int {
var res []int
stack := []*TreeNode{}
for root != nil || len(stack) > 0 {
for root != nil {
stack = append(stack, root)
root = root.Left
}
root = stack[len(stack)-1]
stack = stack[:len(stack)-1]
res = append(res, root.Val)
root = root.Right
}
return res
}
参考文献
94. 二叉树的中序遍历 - leetcode
