非递归中序遍历二叉树

恋喵大鲤鱼

发布于 2022-09-27 21:02:35

5210

文章被收录于专栏：C/C++基础C/C++基础

1.问题描述

非递归中序遍历二叉树。

示例 1：

中序序列：2 1。

示例 2：

中序序列：1 2。

示例 3：

中序序列：2 1 3。

2.难度等级

medium。

3.热门指数

★★★★☆

出题公司：腾讯、B站。

4.解题思路

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

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

/**
 * 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++

/**
 * 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

/**
 * 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
}