Kotlin 二叉树前序遍历（一种递归解决方案，不使用递归）

这篇文章是关于二叉树的前序遍历，一种遍历当前节点先于其子节点访问的树的方法。前序遍历算法首先访问根节点，然后递归访问左子树，然后是右子树。先序遍历的结果是按访问顺序排列的节点值列表。这篇文章将帮助您了解如何遍历二叉树以及如何以不同的方式实现它。

前序遍历是一种遍历二叉树的方法，其中当前节点在其子节点之前被访问。该算法首先访问根节点，然后递归访问左子树，然后是右子树。先序遍历的结果是按访问顺序排列的节点值列表。

在此问题中，您将获得由 Kotlin 中的TreeNode类表示的二叉树的根，该树的节点值具有val属性，其左右子节点分别具有left和right属性。您的任务是编写一个函数的两个实现，该函数执行二叉树的前序遍历并返回节点值的列表。一个应该是递归解决方案，另一个不应该使用递归。

这是该函数的类签名：

 fun preorderTraversal(root: TreeNode?): List<Int>

该函数的输入是二叉树的根节点，输出是一个整数列表，表示节点在先序遍历期间按访问顺序排列的值。

说明：

给定二叉树的根，返回其节点值的前序遍历。使用递归解决方案和不使用递归都可以做到这一点。

 class TreeNode(var `val`: Int) { var left: TreeNode? = null var right: TreeNode? = null }

这是该问题的递归解决方案：

 fun preorderTraversal(root: TreeNode?): List<Int> { val result = mutableListOf<Int>() if (root == null) return result result.add(root.val) result.addAll(preorderTraversal(root.left)) result.addAll(preorderTraversal(root.right)) return result }

此函数对二叉树进行前序遍历，并按访问顺序返回节点值列表。

该算法的工作原理如下：

1. 如果根节点为空，则返回一个空列表。
2. 将根节点的值添加到结果列表。
3. 通过调用根的左孩子上的函数递归遍历左子树，并将返回的列表添加到结果列表中。
4. 通过在根的右孩子上调用函数递归遍历右子树，并将返回的列表添加到结果列表中。
5. 返回结果列表。

该算法的时间复杂度为 O(n)，其中 n 是树中的节点数，空间复杂度为 O(h)，其中 h 是树的高度（由于调用堆栈）。

这是一个使用迭代方法的解决方案（即不使用递归）：

 fun preorderTraversal(root: TreeNode?): List<Int> { val result = mutableListOf<Int>() val stack = Stack<TreeNode>() var current = root while (current != null || stack.isNotEmpty()) { while (current != null) { result.add(current.val) stack.push(current) current = current.left } current = stack.pop() current = current.right } return result }

此函数对二叉树进行前序遍历，并按访问顺序返回节点值列表。它使用堆栈来跟踪仍需要访问的节点。

该算法的工作原理如下：

1. 初始化一个空栈并将当前节点设置为树的根。

2. 当当前节点不为空或堆栈不为空时：

   1. 当前节点不为空时：

      1. 将当前节点的值添加到结果列表中。
      2. 将当前节点压入堆栈。
      3. 将当前节点设置为其左子节点。

   2. 从堆栈中弹出顶部节点并将当前节点设置为它的右子节点。

3. 返回结果列表。

该算法的时间复杂度为 O(n)，其中 n 是树中的节点数，空间复杂度为 O(h)，其中 h 是树的高度。

我希望这有帮助！如果您有任何其他问题，请告诉我。