StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<ol> <li>Your answer is correct. Since the function call on first subtree always returns (regardless the value is found or not), it won't check for next subtrees.</li> <li>You don't have return statement, so at the end of the function Python will implicitly insert <code>return None</code></li> <li>This is already optimal. There is no single Python statement that can do that.</li> <li>The lists (not empty list!) are added because you do <code>return result</code>, and so the parent function call will receive a list (of results) as the result. Then it will append to its local copy of <code>result</code>, and return.</li> <li>You can improve this by not giving <code>result</code> as a parameter:</li> </ol> <pre class="lang-python prettyprint-override"><code>#temp_multi_search v0.25 def temp_multi_search(some_node, key): result = [] # Line 1 if some_node.val == key: print 'found', some_node result.append(some_node) # Line 2 for subtree in some_node.subtrees: result.extend(temp_multi_search(subtree, key)) # Line 3 return result </code></pre> <p>Explanation:</p> <p>It will first check the value on the root node, if it doesn't match, we don't append that node to the search result, otherwise, we add that to our result so far (which would only contain itself). Next we check every subtree.</p> <p>Now, we already know that the function <code>temp_multi_search(subtree, key)</code> will return <strong>all occurrences</strong> on that tree. So after we call <code>temp_multi_search(subtree, key)</code> on each child, we <em>extend</em> the result found in that subtree to our result so far (which might have included the results from previous children).</p> <p>At the end of iterating all children, we return our result.</p> <p>Example:</p> <p>Suppose we are looking for the number <code>1</code> in the following tree, and expects the function to return all occurrences.</p> <pre> 0 _______|________ | | | 1 2 3 _|_ _|_ ___|___ | | | | | | | 1 4 1 5 6 1 7 </pre> <p>So first we call <code>temp_multi_search(root,1)</code>. It's not 1, so <code>result</code> is still empty now.</p> <p>Next we check each subtree:</p> <ol> <li>Child 1: The node value matches, so we add it into the result (at Line 2). Now say we have <code>result = [node1]</code>. Then check each subtree: <ul> <li>GrandChild 1: The node value matches, so we add it into the result (at Line 2). No more subtrees. Return <code>[node2]</code>. The Child 1 call will extend the result <code>[node2]</code> into his result <code>[node1]</code> (Line 3). So the Child 1 now has <code>[node1, node2]</code>.</li> <li>GrandChild 2: Node value doesn't match. No more subtrees. Return []. Child 1 extend empty list, so no change.</li> </ul></li> <li>Child 2: Doesn't match. Check each subtree: <ul> <li>GrandChild 3: Match. Add to result (Line 2). No more subtrees. Return <code>[node5]</code>. Child 2 becomes <code>[node5]</code> (Line 3).</li> <li>GrandChild 4: Doesn't match. No more subtrees. Return []. Child 2 still <code>[node5]</code>.</li> </ul></li> <li>Child 3: Doesn't match. Check each subtree: <ul> <li>GrandChild 5: Doesn't match. No more subtrees. Return []</li> <li>GrandChild 6: Match Add to result (Line 2). Return <code>[node9]</code>. Child 3 will extend it to be <code>[node9]</code> (Line 3)</li> <li>GrandChild 7: Doesn't match. No more subtrees. Return [].</li> </ul></li> </ol> <p>At the end of each mentioned step, the returned result will be extended to Root result by Line 3. So after Step 1, Root result is <code>[node1, node2]</code>. After Step 2, Root result is <code>[node1, node2, node5]</code>. After Step 3, Root result is <code>[node1, node2, node5, node9]</code>.</p> <p>Then after checking all children, return the result.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload