likes
comments
collection
share

二叉树的所有路径

作者站长头像
站长
· 阅读数 28

前言

经过前面的学习，相信我们已经基本了解了二叉树的基本性质了，比如最经典的递归遍历和层序遍历方式，那今天我们就来完成一道二叉树的相关题目，要求是输出所有二叉树从根结点到叶子结点的路径。

LeetCode257

给定一个二叉树，返回所有从根节点到叶子节点的路径。 说明: 叶子节点是指没有子节点的节点。

二叉树的所有路径

基本思路

当我们面对这样的问题时，我们应该考虑以下几个方面：

  1. 遍历二叉树的所有路径：题目要求我们找出从根节点到叶子节点的所有路径。因此，我们需要一种方法来遍历整棵树，并记录从根节点到每个叶子节点的路径。
  2. 递归或迭代：由于我们需要遍历整棵树，并在遍历过程中记录路径，因此递归是一种自然的选择。我们可以使用递归来深度优先搜索树的每条路径。
  3. 路径的表示：我们需要一种方法来表示路径。通常情况下，我们可以使用字符串来表示路径。在遍历的过程中，我们可以将每个节点的值添加到路径字符串中，并使用某种特殊字符（如箭头 ->）来分隔节点值。
  4. 边界条件：在递归的过程中，我们需要处理一些边界情况，比如空节点和叶子节点。

在考虑到这些情况之后，其实发现最适合的方法还是递归，我们可以用一个大数组存放最终结果，然后小数组存放当前结果，每次遇到了叶子结点的时候就可以把结果推入大数组，不然就继续递归遍历求值，应当传入的值是当前结点和路径，因此我们要先写出一个递归函数，最后的结果在递归函数外返回即可。

思路总结

由以上想法我们可以得出以下几点思考：

  1. 深度优先搜索（DFS） ：代码采用深度优先搜索的方式遍历二叉树。通过递归的方式，首先访问左子树，然后访问右子树。
  2. 递归实现：getPath 函数使用了递归来遍历二叉树。它接受当前节点和当前路径作为参数，并在遍历过程中更新路径，直到叶子节点。
  3. 路径记录：代码使用一个数组 arr 来记录从根节点到叶子节点的路径。当遍历到叶子节点时，将路径添加到数组中。
  4. 边界条件处理：在递归的过程中，通过判断当前节点是否为空节点和是否为叶子节点，来处理边界情况。如果当前节点为空，直接返回；如果当前节点为叶子节点，则将路径添加到数组中并返回。
  5. 路径表示：路径使用字符串表示，节点值之间用箭头 "->" 分隔。

代码

// 定义一个函数 binaryTreePaths，接受根节点作为参数
var binaryTreePaths = function(root) {
   // 声明一个空数组用于存储路径
   const arr = []
   
   // 定义递归函数 getPath，用于遍历二叉树并记录路径
   const getPath = (root, path) => {
    // 如果当前节点为空，则直接返回，递归终止条件
    if(!root){
        return null
    }
    // 如果当前节点为叶子节点，即没有左右子节点
    else if(!root.left && !root.right){
        // 将当前节点的值加入路径中，并将完整路径添加到数组中
        path += root.val
        arr.push(path)
        return
    }
    // 如果当前节点不是叶子节点
    else{
        // 将当前节点的值加入路径中，并加入箭头 "->"，表示连接下一个节点
        path += root.val + '->'
        // 递归遍历左子树
        getPath(root.left, path)
        // 递归遍历右子树
        getPath(root.right, path)
    }
   }
   
   // 调用递归函数开始遍历二叉树，初始路径为空字符串
   getPath(root, '')
   
   // 返回存储路径的数组
   return arr
};

  1. var binaryTreePaths = function(root) {：定义了一个函数 binaryTreePaths，该函数接受一个根节点 root 作为参数。

  2. const arr = []：声明了一个空数组 arr，用于存储路径。

  3. const getPath = (root, path) => {：定义了一个名为 getPath 的递归函数，该函数接受当前节点 root 和当前路径 path 作为参数。

  4. if(!root){ return null }：如果当前节点为空（即不存在），则直接返回 null，表示递归结束的基准情况。

  5. else if(!root.left && !root.right){：如果当前节点是叶子节点，即没有左右子节点。

    • path += root.val：将当前叶子节点的值添加到路径末尾。
    • arr.push(path)：将完整的路径添加到数组 arr 中。
    • return：返回，结束当前递归分支。

  6. else{：如果当前节点不是叶子节点，即至少有一个子节点。

    • path += root.val + '->'：将当前节点的值添加到路径末尾，并加上箭头 -> 表示连接下一个节点。
    • getPath(root.left, path)：递归调用 getPath 函数，遍历左子树。
    • getPath(root.right, path)：递归调用 getPath 函数，遍历右子树。

  7. getPath(root, '')：调用 getPath 函数，开始遍历二叉树，初始路径为空字符串。

  8. return arr：返回存储路径的数组 arr。

举个例子

如果还没有理解的话，没有关系，我们跟着一颗具体的二叉树来剖析这段代码吧

    1
   / \
  2   3
     / \
    4   5

现在，我们将按照函数的逻辑来运行代码：

  1. 首先，调用 binaryTreePaths(root) 函数，并传入根节点 root。
  2. 在函数内部，声明一个空数组 arr 用于存储路径。
  3. 定义递归函数 getPath，并调用 getPath(root, '')，其中 root 是当前节点，'' 是初始路径。
  4. 进入 getPath 函数，首先检查当前节点是否为空。由于根节点不为空，进入 else 分支。
  5. 因为根节点不是叶子节点，所以路径 path 更新为 '1->'。
  6. 递归调用 getPath(root.left, path)，遍历左子树。
  7. 对于左子树节点 2，它是叶子节点，因此路径更新为 '1->2'，并将此路径添加到数组 arr 中。
  8. 返回到节点 1，继续执行右子树的遍历。
  9. 对于右子树节点 3，它不是叶子节点，路径更新为 '1->3->'。
  10. 递归调用 getPath(root.left, path)，遍历左子树。
  11. 对于左子树节点 4，它是叶子节点，路径更新为 '1->3->4'，并将此路径添加到数组 arr 中。
  12. 返回到节点 3，继续执行右子树的遍历。
  13. 对于右子树节点 5，它是叶子节点，路径更新为 '1->3->5'，并将此路径添加到数组 arr 中。
  14. 递归结束，函数返回数组 arr，其中包含了所有从根节点到叶子节点的路径。
  15. 最终，返回的数组 arr 包含了所有路径 ['1->2', '1->3->4', '1->3->5']。

总结

经过这道题，我们可以有以下收获

  1. 二叉树的递归遍历：代码中使用了递归的方式来遍历二叉树。递归是一种在函数内部调用自身的技术，在这里用于遍历树的节点。
  2. 处理二叉树节点：通过检查节点的左右子节点情况，可以确定当前节点的类型（叶子节点还是非叶子节点）。这有助于确定何时应该停止遍历并处理路径。
  3. 路径的构建和存储：代码中使用 path 变量来构建当前节点到根节点的路径，并将该路径存储在数组 arr 中。这种方式可以有效地记录从根节点到叶子节点的所有路径。
  4. 数组的返回：函数最终返回存储路径的数组 arr，其中包含了所有从根节点到叶子节点的路径。这种设计使得函数的输出易于使用和处理。
  5. 函数参数的传递：通过函数参数的传递，可以在递归调用中传递状态信息，例如当前路径。在这段代码中，path 参数用于传递当前节点到根节点的路径。
  6. 对二叉树节点的检查：通过检查节点是否为空，可以避免在空节点上进行操作，从而避免出现错误。

相信我们对二叉树和递归的了解一定又更上一层楼了呢！

转载自:https://juejin.cn/post/7361401330990874658
评论
请登录