文章目录
- 1.问题描述
- 2.难度等级
- 3.热门指数
- 4.解题思路
- 5.实现示例
- 5.1 C
- 5.2 Golang
- 参考文献
1.问题描述
非递归中序遍历二叉树。
示例 1：
中序序列：2 1。
示例 2：
中序序列：1 2。
示例 3：
中序序列：2 1 3。
2.难度等级
medium。
3.热门指数
★★★★☆
出题公司：腾讯、B站。
4.解题思路
中序遍历按照“左子树 > 根结点 > 右子树”的顺序进行访问。而在访问左子树或右子树的时候我们按照同样的方式遍历，直到遍历完整棵树。
因此整个遍历过程天然具有递归的性质，我们可以直接用递归函数来模拟这一过程。
以 Golang 为例给出递归的实现示例。
代码语言：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
}递归很简单，如何使用非递归的方式中序遍历呢？
只要是递归，便可以使用栈模拟递归的过程。
根据中序遍历的顺序，对于根结点，先访问其左孩子，而左孩子又可以看做一根结点，然后继续访问其左孩子，直到遇到左孩子为停止访问，然后按相同的规则访问其右子树。因此其处理过程如下：
对于给定的二叉树根结点 R， （1）若其左孩子不为空，循环将 R 及其左结点入栈，直至左结点为空； （2）访问栈顶元素 cur 并出栈。然后对 cur 的右子结点进行步骤（1）那样的处理； （3）重复（1）和（2）的操作，直到 cur 为空且栈为空。
复杂度分析：
时间复杂度：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
