写点什么

手撸二叉树之二叉树的所有路径

发布于: 2021 年 09 月 10 日
手撸二叉树之二叉树的所有路径

Hello, 大家好,今天是我参加 9 月更文的第 3 天,今天给大家带来的关于二叉树相关的算法题是二叉树的所有路径,正文如下:

题目

给定一个二叉树,返回所有从根节点到叶子节点的路径。


说明: 叶子节点是指没有子节点的节点。


示例:


输入:
1 / \2 3 \ 5
输出: ["1->2->5", "1->3"]
解释: 所有根节点到叶子节点的路径为: 1->2->5, 1->3
复制代码

解题思路

根据题意我们可以使用深度优先搜索的方式来解答此题。


解题思路如下:


  1. 首先我们需要创建一个数组用于保存路径;

  2. 如果当前节点是叶子节点,则在当前路径末尾添加该节点后,就得到了一条从根节点到叶子节点的路径,并把该条路径加入到答案数组中;

  3. 如果当前节点不是叶子节点,则在当前路径末尾添加这个节点,并继续递归遍历该节点的左子树和右子树;


当遍历完整棵二叉树以后,我们就得到了所有从根节点到叶子节点的路径。

代码实现

/** * Definition for a binary tree node. * public class TreeNode { *     int val; *     TreeNode left; *     TreeNode right; *     TreeNode() {} *     TreeNode(int val) { this.val = val; } *     TreeNode(int val, TreeNode left, TreeNode right) { *         this.val = val; *         this.left = left; *         this.right = right; *     } * } */class Solution {    public List<String> binaryTreePaths(TreeNode root) {        List<String> paths = new ArrayList();        constructPath(root, "", paths);        return paths;    }
// 自顶向下遍历 public void constructPath(TreeNode node, String path, List<String> paths){ if (node != null){ StringBuilder pathSB = new StringBuilder(path); pathSB.append(Integer.toString(node.val)); if (node.left == null && node.right == null){ paths.add(pathSB.toString()); } else { pathSB.append("->"); constructPath(node.left, pathSB.toString(), paths); constructPath(node.right, pathSB.toString(), paths); } } }}
复制代码

最后

复杂度分析:


  • 时间复杂度:O(N^2),其中 N 表示节点数目。在深度优先搜索中每个节点会被访问一次且只会被访问一次,每一次会对 path 变量进行拷贝构造,时间代价为 O(N),故时间复杂度为 O(N^2)。

  • 空间复杂度:O(N^2),其中 N 表示节点数目。除答案数组外我们需要考虑递归调用的栈空间。

发布于: 2021 年 09 月 10 日阅读数: 5
用户头像

佛系编码 2019.05.13 加入

红鲤鱼与绿鲤鱼与驴。

评论

发布
暂无评论
手撸二叉树之二叉树的所有路径