Binary Tree Paths 480
Question
Given a binary tree, return all root-to-leaf paths.
Example
Given the following binary tree:
1 / \ 2 3 \ 5
All root-to-leaf paths are:
[ "1->2->5",
"1->3" ]
Solution
Divide and Conquer.
九章给的答案是recursion.
代码如下:
D&C:
/**
* 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<String> result = new ArrayList<String>();
if(root == null){
return result;
}
if(root.left == null && root.right == null){
result.add(String.valueOf(root.val));
}
List<String> left = binaryTreePaths(root.left);
List<String> right = binaryTreePaths(root.right);
if(left.size() != 0){
for(String s : left){
StringBuilder sb = new StringBuilder();
sb.append(root.val);
sb.append("->");
sb.append(s);
result.add(sb.toString());
}
}
if(right.size() != 0){
for(String s : right){
StringBuilder sb = new StringBuilder();
sb.append(root.val);
sb.append("->");
sb.append(s);
result.add(sb.toString());
}
}
return result;
}
}
Recursion:
public class Solution {
/**
* @param root the root of the binary tree
* @return all root-to-leaf paths
*/
public List<String> binaryTreePaths(TreeNode root) {
List<String> result = new ArrayList<String>();
if (root == null) {
return result;
}
helper(root, String.valueOf(root.val), result);
return result;
}
private void helper(TreeNode root, String path, List<String> result) {
if (root == null) {
return;
}
if (root.left == null && root.right == null) {
result.add(path);
return;
}
if (root.left != null) {
helper(root.left, path + "->" + String.valueOf(root.left.val), result);
}
if (root.right != null) {
helper(root.right, path + "->" + String.valueOf(root.right.val), result);
}
}
}