Given a binary tree, return all root-to-leaf paths.
Note: A leaf is a node with no children.
GeeksforGeeks
ProgramCreek
YouTube
Input: [1, 2, 3, null, 5]
Output: ["1->2->5", "1->3"]
Input: [1, 2, 3, null, 5, 6, 7, 8, 9]
Output: ["1->2->5->8", "1->2->5->9", "1->3->6", "1->3->7"]
Input: [1]
Output: ["1"]
Last updated
Was this helpful?
Was this helpful?
// Definition for a binary tree node.
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode() {}
TreeNode(int val) {
this.val = val;
}
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}/**
* Time complexity : O(N)
* Space complexity : O(N)
*/
class Solution {
private List<String> resultList;
public List<String> binaryTreePaths(TreeNode root) {
resultList = new ArrayList();
constructPath(root, new StringBuilder());
return resultList;
}
private void constructPath(TreeNode node, StringBuilder path) {
if(node == null) {
return;
}
int len = path.length();
path.append(node.val);
if(node.left == null && node.right == null) {
resultList.add(path.toString());
} else {
path.append("->");
}
constructPath(node.left, path);
constructPath(node.right, path);
path.setLength(len);
}
}/**
* Time complexity : O(N)
* Space complexity : O(N)
*/
class Solution {
public List<String> binaryTreePaths(TreeNode root) {
List<String> resultList = new ArrayList();
if(root == null) {
return resultList;
}
Stack<TreeNode> nodeStack = new Stack();
Stack<String> pathStack = new Stack();
nodeStack.push(root);
pathStack.push(Integer.toString(root.val));
while(!nodeStack.isEmpty()) {
TreeNode curr = nodeStack.pop();
String path = pathStack.pop();
if(curr.left == null && curr.right == null) {
resultList.add(path);
}
if(curr.left != null) {
nodeStack.push(curr.left);
pathStack.push(path + "->" + Integer.toString(curr.left.val));
}
if(curr.right != null) {
nodeStack.push(curr.right);
pathStack.push(path + "->" + Integer.toString(curr.right.val));
}
}
return resultList;
}
}