给一棵二叉树,找出从根节点到叶子节点的所有路径。
样例
给出下面这棵二叉树:
1
/ \
2 3
\
5
所有根到叶子的路径为:
[
"1->2->5",
"1->3"
]
解:很经典的一道题,很简单但是还是有一些注意的点。
先上代码
/** * Definition of TreeNode: * public class TreeNode { * public int val; * public TreeNode left, right; * public TreeNode(int val) { * this.val = val; * this.left = this.right = null; * } * } */ public class Solution { /* * @param root: the root of the binary tree * @return: all root-to-leaf paths */ public List<String> binaryTreePaths(TreeNode root) { // write your code here List<List<Integer>> ans = new ArrayList<List<Integer>>(); List<Integer> temp = new ArrayList<Integer>(); List<Integer> temptemp; List<String> ansrel = new ArrayList<String>(); if(root == null){ return ansrel; } work(root,ans,temp); for(int i = 0; i<ans.size(); i++){ temptemp = ans.get(i); String tmp = ""; for(int j = 0; j<temptemp.size(); j++){ if(j == temptemp.size()-1){ tmp = tmp+temptemp.get(j)+""; }else{ tmp = tmp+temptemp.get(j)+"->"; } } ansrel.add(tmp); } return ansrel; } public void work(TreeNode root,List<List<Integer>> ans,List<Integer> temp){ if(root.left == null&&root.right == null){ temp.add(root.val); ans.add(new ArrayList<Integer>(temp)); temp.remove(temp.size()-1); }else if(root.left == null){ temp.add(root.val); work(root.right,ans,temp); temp.remove(temp.size()-1); }else if(root.right == null){ temp.add(root.val); work(root.left,ans,temp); temp.remove(temp.size()-1); }else{ temp.add(root.val); work(root.left,ans,temp); work(root.right,ans,temp); temp.remove(temp.size()-1); } return; } }
这道题还算简单。 每次一层放入当前节点 然后左右子树递归调用,然后当前层返回之前把当前层的值remove掉。
存进去的条件是没有左右子树。(如果插入条件写成为空的话,会出现重复的情况,会把一个节点的左右空子树放进去,各自生成一个,但是是一样的)
最后给转化成那种字符串形式。 注意这里的列表是索引传递 需要ans.add(new ArrayList(temp));
这样写