Binary Tree Paths
最近,在https://leetcode.com上开始做些算法题,因为平时不咋捉摸算法,只是工作中用到的,才会接触写,工作已经六年了,记得只有一次大概是10年时设计到一个算法题转化为纯数学题,在演算纸上演算,得到结果后,翻译为代码,以后基本上没有接触到多少算法,当然找工作前也大概看了下的。
言归正传,在leetcode上的题做些记录,从简单地开始。
题的描述:
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"]
自己完成的代码:
package com.leetcode.algrithm.binarytreepath; import java.util.ArrayList; import java.util.List; public class Solution { public static void main(String[] args) { Solution t = new Solution(); TreeNode a = t.new TreeNode(1); TreeNode b = t.new TreeNode(2); TreeNode c = t.new TreeNode(3); TreeNode d = t.new TreeNode(4); TreeNode e = t.new TreeNode(5); a.left = b; a.right = c; b.right = e; b.left = d; System.out.println(t.binaryTreePaths(a)); } public List<String> binaryTreePaths(TreeNode root) { List<String> resultList = new ArrayList<String>(); if (root == null){ return resultList; } if (root.left==null && root.right==null){ resultList.add(""+root.val); } if (root.left!=null ){ resultList.addAll(binaryTreePaths2("\""+root.val,root.left)); } if (root.right!=null){ resultList.addAll(binaryTreePaths2("\""+root.val,root.right)); } return resultList; } public static List<String> binaryTreePaths2(String prefix,TreeNode root){ List<String> result = new ArrayList<String>(); if (root.left == null && root.right == null){ result.add(prefix + "->"+root.val+"\""); } if (root.left!=null ){ result.addAll(binaryTreePaths2(prefix+ "->"+root.val,root.left)); } if (root.right!=null){ result.addAll(binaryTreePaths2(prefix+ "->"+root.val,root.right)); } return result; } public class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val = x; } } }
测试结果:
["1->2->4", "1->2->5", "1->3"]
测试通过,本算法原来实现时,递归左子树和右子树时时这样
if (root.left!=null ){ return "->"+root.val+binaryTreePaths2(root.left)); } if (root.right!=null ){ return "->"+root.val+binaryTreePaths2(root.right)); }但是这样有个问题,当root具有左子树和右子树时,那么因为左子树进行递归,递归后直接return,右子树就没有被递归执行,所以后来调整为上述正确的程序。
« 韭菜园正式上线
|
Redis设计与实现——链表»
评论:
日历
个人资料
![blogger](http://www.jiucaiyuan.net/content/uploadfile/201509/thum-623a1441115314.jpg)
diaba 寻求合作请留言或联系mail: services@jiucaiyuan.net
链接
最新文章
存档
- 2024年8月(2)
- 2024年6月(4)
- 2024年5月(1)
- 2023年7月(1)
- 2022年10月(1)
- 2022年8月(1)
- 2022年6月(11)
- 2022年5月(6)
- 2022年4月(33)
- 2022年3月(26)
- 2021年3月(1)
- 2020年9月(2)
- 2018年8月(1)
- 2018年3月(1)
- 2017年3月(3)
- 2017年2月(6)
- 2016年12月(3)
- 2016年11月(2)
- 2016年10月(1)
- 2016年9月(3)
- 2016年8月(4)
- 2016年7月(3)
- 2016年6月(4)
- 2016年5月(7)
- 2016年4月(9)
- 2016年3月(4)
- 2016年2月(5)
- 2016年1月(17)
- 2015年12月(15)
- 2015年11月(12)
- 2015年10月(6)
- 2015年9月(11)
- 2015年8月(8)
分类
热门文章
- SpringMVC:Null ModelAndView returned to DispatcherServlet with name 'applicationContext': assuming HandlerAdapter completed request handling
- Mac-删除卸载GlobalProtect
- java.lang.SecurityException: JCE cannot authenticate the provider BC
- MyBatis-Improper inline parameter map format. Should be: #{propName,attr1=val1,attr2=val2}
- Idea之支持lombok编译
标签
最新评论
- logisqykyk
Javassist分析、编辑和创建jav... - xxedgtb
Redis—常见参数配置 - 韭菜园 ... - wdgpjxydo
SpringMVC:Null Model... - rllzzwocp
Mysql存储引擎MyISAM和Inno... - dpkgmbfjh
SpringMVC:Null Model... - tzklbzpj
SpringMVC:Null Model... - bqwrhszmo
MyBatis-Improper inl... - 乐谱吧
good非常好 - diaba
@diaba:应该说是“时间的度量依据”... - diaba
如果速度增加接近光速、等于光速、甚至大于...
最新微语
- 从今天起,做一个幸福的人。喂马,砍柴,(思想)周游世界
2022-03-21 23:31
- 2022.03.02 23:37:59
2022-03-02 23:38
- 几近崩溃后,找到解决方法,总是那么豁然开朗!所以遇到问题要坚持!
2018-07-18 10:49
- 2018年关键字“走心”
2018-03-19 16:07
- 保护好自己最大的方法是让自己更强大,不要柔弱的像一只绵羊一样,得谁巴拉,就谁巴拉!
2017-12-20 10:24
2016-07-29 16:05