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

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

今天给大家带来的关于二叉树相关的算法题是二叉树的所有路径，正文如下：

题目

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

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

示例：

输入: 1 / \2 3 \ 5输出: ["1->2->5", "1->3"]解释: 所有根节点到叶子节点的路径为: 1->2->5, 1->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 binaryTreePaths(TreeNode root) { List paths = new ArrayList(); constructPath(root, "", paths); return paths; } // 自顶向下遍历 public void constructPath(TreeNode node, String path, List 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 表示节点数目。除答案数组外我们需要考虑递归调用的栈空间。

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。