[LeetCode] Binary Tree Paths 二叉树路径

[LeetCode] Binary Tree Paths 二叉树路径

Given a binary tree, return all root-to-leaf paths.

For example, given the following binary tree:

1 / \2 3 \ 5

All root-to-leaf paths are:

["1->2->5", "1->3"]

​​图形化表述:​​

import java.util.List;import java.util.ArrayList;public class liubobo_7_4 {/// 257. Binary Tree Paths/// 时间复杂度: O(n), n为树中的节点个数/// 空间复杂度: O(h), h为树的高度 // Definition for a binary tree node. public class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val = x; } } public List binaryTreePaths(TreeNode root) { ArrayList res = new ArrayList(); if(root == null)//递归终止条件，防止放入空树 return res; if(root.left == null && root.right == null){//递归终止条件，判断有没有到达叶子节点 res.add(Integer.toString(root.val)); return res; } List leftPaths = binaryTreePaths(root.left);//返回所有左子树的路径 for(String s: leftPaths){ StringBuilder sb = new StringBuilder(Integer.toString(root.val)); sb.append("->"); sb.append(s); res.add(sb.toString()); } List rightPaths = binaryTreePaths(root.right);//返回所有右子树的路径 for(String s: rightPaths) { StringBuilder sb = new StringBuilder(Integer.toString(root.val)); sb.append("->"); sb.append(s); res.add(sb.toString()); } return res; }}

类似题目:

1.path sum II

2.sum root to leaf numbers

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