二叉树的所有路径

题目思路代码算法复杂度

题目来源于leetcode，解法和思路仅代表个人观点。传送门。 难度：简单 用时：10分钟左右(比较简单

题目

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

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

示例:

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

思路

DFS 当前结点的路径 = 当前结点值 + “->” + 子节点的路径

代码

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public List<String> binaryTreePaths(TreeNode root) { if(root == null){ return new ArrayList<String>(); } List<String> ans = new ArrayList<>(); List<String> leftPaths = binaryTreePaths(root.left); List<String> rightPaths = binaryTreePaths(root.right); //如果当前结点不是叶子节点 ans.addAll(leftPaths); ans.addAll(rightPaths); for(int i=0;i<ans.size();i++){ String temp = String.valueOf(root.val) + "->" + ans.get(i); ans.set(i,temp); } //如果当前结点是叶子节点 if(leftPaths.size() == 0 && rightPaths.size() == 0){ ans.add(String.valueOf(root.val)); } return ans; } }

算法复杂度

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