二叉树的中序遍历（LeetCode 94）_leetcode94

1.问题描述

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

示例 1：

中序序列：2 1。

示例 2：

中序序列：1 2。

示例 3：

中序序列：2 1 3。

2.难度等级

Easy。

3.热门指数

★★★★★

出题公司：腾讯、B站。

4.解题思路

方法一：递归

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

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

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

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

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

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func inorderTraversal(root *TreeNode) []int {
    var r []int

    // 中序遍历的递归函数。
    var inorder func(node *TreeNode)
    inorder = func(node *TreeNode) {
		if node == nil {
			return
		}
		inorder(node.Left)
		r = append(r, node.Val)
		inorder(node.Right)
	}

    // 中序遍历。
    inorder(root)
    return r
}

// 下面这种写法也可以。
func inorderTraversal(root *TreeNode) []int {
    if root == nil {
        return nil
    }
    left := inorderTraversal(root.Left)
    nodes := append(left, root.Val)
    right := inorderTraversal(root.Right)
    nodes = append(nodes, right...)
    return nodes
}
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
29
30
31
32
33
34
35
36
37
38

方法二：迭代

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

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

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

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

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

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

Golang

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func inorderTraversal(root *TreeNode) []int {
    var res []int
    var stack *TreeNode
	for root != nil || len(stack) > 0 {
		for root != nil {
			stack = append(stack, root)
			root = root.Left
		}
		root = stack[len(stack)-1]
		res = append(res, root.Val)
		// 出栈
		stack = stack[:len(stack)-1]
		// 迭代右子树
		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

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) {}
 * };
 */
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

---

参考文献

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