Open Shawngbk opened 7 years ago
DFS
SOL1: public class Solution { public List binaryTreePaths(TreeNode root) { List res = new ArrayList<>(); if(root != null) SearchDFS(root, "", res); return res; }
private void SearchDFS(TreeNode root, String path, List<String> res) { if(root.left == null && root.right == null) res.add(path + root.val); if(root.left != null) SearchDFS(root.left, path + root.val + "->", res); if(root.right != null) SearchDFS(root.right, path + root.val + "->", res); }
}
Sol.2 public List binaryTreePaths(TreeNode root) { List res = new ArrayList<>(); if(root == null) return res; String path = new String(); TreeNode p = root; Stack stack = new Stack<>(); Stack pathStack = new Stack<>(); TreeNode pre = null; while(p!=null || !stack.isEmpty()) { if(p!=null) { if(p == root) path = Integer.toString(p.val); else path = path+"->"+Integer.toString(p.val);
if(p.left == null && p.right == null) res.add(path); pathStack.push(path); stack.push(p); pre = p; p = p.left; } else { TreeNode node = stack.pop(); p = node.right; path = pathStack.pop(); } } return res;
Apple FB Google
DFS
SOL1: public class Solution { public List binaryTreePaths(TreeNode root) {
List res = new ArrayList<>();
if(root != null)
SearchDFS(root, "", res);
return res;
}
}
Sol.2 public List binaryTreePaths(TreeNode root) {
List res = new ArrayList<>();
if(root == null)
return res;
String path = new String();
TreeNode p = root;
Stack stack = new Stack<>();
Stack pathStack = new Stack<>();
TreeNode pre = null;
while(p!=null || !stack.isEmpty())
{
if(p!=null)
{
if(p == root)
path = Integer.toString(p.val);
else
path = path+"->"+Integer.toString(p.val);
}