非递归中序遍历二叉树

1.问题描述

非递归中序遍历二叉树。

示例 1：

中序序列：2 1。

示例 2：

中序序列：1 2。

示例 3：

中序序列：2 1 3。

2.难度等级

medium。

3.热门指数

★★★★☆

出题公司：腾讯、B站。

4.解题思路

中序遍历按照“左子树 > 根结点 > 右子树”的顺序进行访问。而在访问左子树或右子树的时候我们按照同样的方式遍历，直到遍历完整棵树。

因此整个遍历过程天然具有递归的性质，我们可以直接用递归函数来模拟这一过程。

以 Golang 为例给出递归的实现示例。

/**
 * 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
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

递归很简单，如何使用非递归的方式中序遍历呢？

只要是递归，便可以使用栈模拟递归的过程。

根据中序遍历的顺序，对于根结点，先访问其左孩子，而左孩子又可以看做一根结点，然后继续访问其左孩子，直到遇到左孩子为停止访问，然后按相同的规则访问其右子树。因此其处理过程如下：

对于给定的二叉树根结点 R，
（1）若其左孩子不为空，循环将 R 及其左结点入栈，直至左结点为空；
（2）访问栈顶元素 cur 并出栈。然后对 cur 的右子结点进行步骤（1）那样的处理；
（3）重复（1）和（2）的操作，直到 cur 为空且栈为空。

复杂度分析：

时间复杂度：O(n)，其中 n 为二叉树结点的个数。二叉树的遍历中每个结点会被访问一次且只会被访问一次。

空间复杂度：O(n)。空间复杂度取决于递归的栈深度，而栈深度在二叉树为一条链的情况下会达到 O(n) 的级别。

5.实现示例

5.1 C++

/**
 * 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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

5.2 Golang

/**
 * 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
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

---

参考文献

94. 二叉树的中序遍历 - leetcode