Does the solution really passed case 2???
Yes
Do not need to add and remove each time in the children for loop.
Can simply add the root.val before for-loop and remove it after the for-loop in optimized solution. I think it makes it more readable as well.
It throws error “Exception in thread “main” java.lang.NullPointerException: Cannot read the array length because “” is null
at Solution.main(Solution.java:57)”.
Actually why can’t you just pass a string path rather than an arraylist in dfs method?
appending to string is O(n).
It’s disappointing that (yet again) there’s no starting C++ version for this; here’s mine:
#include // copy
#include // cin, cout
#include // back_inserter, istream_iterator, ostream_iterator, prev
#include // istringstream
#include // getline, stoi, string, to_string
#include // vector
template
struct Node {
T val;
Node* left;
Node* mid;
Node* right;
explicit Node(T val, Node<T>* left = nullptr, Node<T>* mid = nullptr, Node<T>* right = nullptr)
: val{val}, left{left}, mid{mid}, right{right} {}
~Node() {
delete left;
delete mid;
delete right;
}
};
void print_paths(Node* root, std::string const s)
{
if (root == nullptr) return;
std::ostringstream oss;
oss << s << root->val;
if (root->left == nullptr and root->mid == nullptr and root->right == nullptr)
{
std::cout << oss.str() << std::endl;
return;
}
oss << “->”;
print_paths(root->left, oss.str());
print_paths(root->mid, oss.str());
print_paths(root->right, oss.str());
}
void tree_paths(Node* tree) {
print_paths(tree, std::string());
}
template<typename T, typename Iter, typename F>
Node* build_tree(Iter& it, F f) {
std::string val = it;
++it;
if (val == “x”) return nullptr;
Node left = build_tree(it, f);
Node* mid = build_tree(it, f);
Node* right = build_tree(it, f);
return new Node{f(val), left, mid, right};
}
template
std::vector get_words() {
std::string line;
std::getline(std::cin, line);
std::istringstream ss{line};
std::vector v;
std::copy(std::istream_iterator{ss}, std::istream_iterator{}, std::back_inserter(v));
return v;
}
int main() {
std::vectorstd::string tree_vec = get_wordsstd::string();
auto tree_it = tree_vec.begin();
Node* tree = build_tree(tree_it, [](auto s) { return std::stoi(s); });
tree_paths(tree);
}
It should now be fixed.
The line below:
dfs(child, path + [root.val], res)
Should be:
dfs(child, path + [str(root.val)], res)
Otherwise, it throws an error.
This is a good tip. Also found this to work:
- append to path as the first line in the recursive function
- pop from path at all exit points, 1 for leaf case, 1 for non-leaf
After doing more of these questions, it seems the template is best. While in this problem, the next_state does not depend on child, in many problems next_state does. In general, append-dfs-pop always works.
You can. Use StringBuilder in Java to append string.
ArrayList better way I feel.
My Solution:
static List result = new ArrayList<>();
public static void util(Node<Integer> root,String state) {
// WRITE YOUR BRILLIANT CODE HERE
if(root.children.size()==0){
result.add(state.substring(0,state.length()-2));
return;
}
for(Node n : root.children){
String s = (state.concat(String.valueOf(n.val))).concat("->");
util(n,s);
}
return ;
}
public static List<String> ternaryTreePaths(Node<Integer> root) {
// WRITE YOUR BRILLIANT CODE HERE
util(root,Integer.toString(root.val).concat("->"));
return result;
}
Why are we checking for the first three elements of children?
if (root.children[0] == null && root.children[1] == null && root.children[2] == null)
I try your code but it’s not pass. It is exactly the same code as the solution.
The Python Code is wrong
Here is the fix:
def ternary_tree_paths(root: Node) → List[str]:
# WRITE YOUR BRILLIANT CODE HERE
answer = []
def dfs(root, path, res):
if all(c is None for c in root.children):
res.append(“->”.join(path) + “->” + str(root.val))
return
path.append(str(root.val))
for child in root.children:
if child:
dfs(child, path, res)
path.pop()
dfs(root, [], answer)
return answer
This solution is incorrect, or at the least just throwing a runtime error.
Can you elaborate?
hi, sorry we had a server issue and the backup server had older commits which didn’t have c# boilerplate for many questions. it’s fixed now. let me know if there’s anything you find that need to be added.