给你一个二叉树的根节点 root
,按 任意顺序 ,返回所有从根节点到叶子节点的路径。
叶子节点 是指没有子节点的节点。
输入:root = [1,2,3,null,5]
输出:["1->2->5","1->3"]
递归,将list作为参数传递
class Solution { public List<String> binaryTreePaths(TreeNode root) { List<String> list = new ArrayList<>(); if(root==null) return list; helper(root, "", list); return list; } public void helper(TreeNode root, String path, List<String> list){ if(root == null) return; if(root.left == null && root.right == null) list.add(path + root.val); else{ helper(root.left, path+root.val+"->", list); helper(root.right, path+root.val+"->", list); } } }
递归,将list作为全局变量
class Solution { List<String> list = new ArrayList<>(); public List<String> binaryTreePaths(TreeNode root) { helper(root, ""); return list; } public void helper(TreeNode root, String path){ if(root == null) return; if(root.left == null && root.right == null) list.add(path + root.val); else{ helper(root.left, path+root.val+"->"); helper(root.right, path+root.val+"->"); } } }
递归,将list作为返回值
class Solution { public List<String> binaryTreePaths(TreeNode root) { return helper(root, ""); } public List helper(TreeNode root, String path){ List<String> list = new ArrayList<>(); if(root == null) return list; if(root.left == null && root.right == null) list.add(path + root.val); else{ list.addAll(helper(root.left, path+root.val+"->")); list.addAll(helper(root.right, path+root.val+"->")); } return list; } }
迭代
class Solution { public List<String> binaryTreePaths(TreeNode root) { List<String> paths = new ArrayList<String>(); if (root == null) return paths; Queue<TreeNode> nodeQueue = new LinkedList<TreeNode>(); Queue<String> pathQueue = new LinkedList<String>(); nodeQueue.offer(root); pathQueue.offer(Integer.toString(root.val)); while (!nodeQueue.isEmpty()) { TreeNode node = nodeQueue.poll(); String path = pathQueue.poll(); if (node.left == null && node.right == null) { paths.add(path); } else { if (node.left != null) { nodeQueue.offer(node.left); pathQueue.offer(new StringBuffer(path).append("->").append(node.left.val).toString()); } if (node.right != null) { nodeQueue.offer(node.right); pathQueue.offer(new StringBuffer(path).append("->").append(node.right.val).toString()); } } } return paths; } }
知识点:无
总结:无