Leetcode[257] Binary Tree Paths
01 Dec 2015###Task1 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”]
###Python ###dfs
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def binaryTreePaths(self, root):
"""
:type root: TreeNode
:rtype: List[str]
"""
ret = []
if not root:
return ret
self.dfs(root, str(root.val), ret)
return ret
def dfs(self, root, path, ret):
if not root.left and not root.right:
ret.append(path)
if root.left:
self.dfs(root.left, path + '->' + str(root.left.val), ret)
if root.right:
self.dfs(root.right, path + '->' + str(root.right.val), ret)
####bfs
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def binaryTreePaths(self, root):
"""
:type root: TreeNode
:rtype: List[str]
"""
if not root:
return []
queue = []
queue.append([root, str(root.val)])
ret = []
while queue:
front, path = queue.pop(0)
if not front.left and not front.right:
ret.append(path)
continue
if front.left:
queue.append([front.left, path + '->' + str(front.left.val)])
if front.right:
queue.append([front.right, path + '->' + str(front.right.val)])
return ret
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def binaryTreePaths(self, root):
"""
:type root: TreeNode
:rtype: List[str]
"""
if not root:
return []
ret = []
self.helper(root, ret, [])
return ret
def helper(self, root, ret, temp):
if len(temp) == 0:
temp.append(str(root.val))
else:
temp.append('->' + str(root.val))
if not root.left and not root.right:
ret.append(''.join(temp))
return
if root.left:
self.helper(root.left, ret, temp[:])
if root.right:
self.helper(root.right, ret, temp[:])
return
save memory
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def binaryTreePaths(self, root):
"""
:type root: TreeNode
:rtype: List[str]
"""
if not root:
return []
ret = []
self.helper(root, ret, [])
return ret
def helper(self, root, ret, temp):
if len(temp) == 0:
temp.append(str(root.val))
else:
temp.append('->' + str(root.val))
if not root.left and not root.right:
ret.append(''.join(temp))
return
if root.left:
self.helper(root.left, ret, temp)
temp.pop()
if root.right:
self.helper(root.right, ret, temp)
temp.pop()
return
###Java
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
// wocao:
// 不能用sb， 因为会有负号！！
public class Solution {
public int[] levelVal = new int[1000];
public void helper(List<String> res, TreeNode root, int level) {
if (root == null) {
return;
}
levelVal[level] = root.val;
if (root.left == null && root.right == null) {
addToRes(res, level);
}
helper(res, root.left, level + 1);
helper(res, root.right, level + 1);
}
public void addToRes(List<String> res, int level) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < level; i++) {
sb.append(levelVal[i]);
sb.append("->");
}
sb.append(levelVal[level]);
res.add(sb.toString());
return;
}
public List<String> binaryTreePaths(TreeNode root) {
List<String> res = new ArrayList<String>();
if (root == null) {
return res;
}
helper(res, root, 0);
return res;
}
}
###Points
- Binary tree traversal –> bfs / dfs
- dfs :1. end condition: not left and not right 2. continue step: add ‘->#’