I am doing Leet Code question 572. Subtree of Another Tree:
Given the roots of two binary trees
root
andsubRoot
, returntrue
if there is a subtree ofroot
with the same structure and node values ofsubRoot
andfalse
otherwise.A subtree of a binary tree
tree
is a tree that consists of a node intree
and all of this node's descendants. The treetree
could also be considered as a subtree of itself.
I had a working solution. However, when trying a slightly different approach, I ran into a problem with my recursive dfs function. The structure of my code is this:
def isSubTree(self, root, subRoot):
def dfs(root, subRoot):
# some function that returns True when certain conditions are met
if not root: return
self.isSubtree(root.left, subRoot)
self.isSubtree(root.right, subRoot)
if root.val == subRoot.val:
if dfs(root, subRoot):
return True
return False
Basically, isSubTree
explores all the nodes in the tree. Once it finds a node with the same value as subRoot
, it compares the sub tree rooted at that node with the sub tree rooted at subRoot
with dfs()
.
I intended that when the dfs()
function returns true, isSubTree()
will also return true. If I've explored all the nodes in the tree (isSubTree()
reaches the end) and dfs()
hasn't returned true
at all, isSubTree()
will return False.
However,my code always returns false seemingly because of the last line where it returns False
(I've tested it and can verify that the return True
part in if dfs()
was reached, also I'm pretty sure my dfs()
function is correct).
My question is, is there an elegant way to have my code do what I want it to do?
CodePudding user response:
It is hard to see which code you are using, since obviously there is a syntax problem just below def dfs
. Either the indentation is off or there is code missing (at the time of writing).
There are these issues:
The returned value from either recursive
self.isSubTree
calls is not used at all. This cannot be right, as certainly you need that information to conclude anything about the work done.if not root: return
will not return a boolean value when it kicks in. This should make the distinction between the case where alsosubTree
isNone
: in that case the returned value should beTrue
. Otherwise it should beFalse
Assuming your non-provided
dfs
code is correct, it will deal well with the previous point as well (where one or both of the arguments isNone
), and will compare the node values correctly, so thenif not root
should not be performed beforedfs
is called, asdfs
will take care of that.Similarly
if root.val == subTree.val
should not have to occur where it now occurs, but only indfs
.
Concluding, the working code could be like this:
class Solution(object):
def isSubtree(self, root, subRoot):
def dfs(root, subRoot):
if not root or not subRoot or root.val != subRoot.val:
return root == subRoot # Must both be None to have success
return dfs(root.left, subRoot.left) and dfs(root.right, subRoot.right)
return dfs(root, subRoot) or root and (
self.isSubtree(root.left, subRoot) or self.isSubtree(root.right, subRoot)
)
CodePudding user response:
As far I understand, you want to the isSubTree to return True
if dfs()
returns True
for at least one of recursive branches.
You will need the isSubTree
function to immediately return True
if one of the branches finds a solution:
def isSubTree(self, root, subRoot):
def dfs(root, subRoot):
# some function that returns True when certain conditions are met
if not root: return
if self.isSubtree(root.left, subRoot):
return True
if self.isSubtree(root.right, subRoot):
return True
if root.val == subRoot.val:
if dfs(root, subRoot):
return True
return False
You need the intermediate nodes in the recursion tree to transmit the information upwards if any of their children has found the solution. Otherwise you discard the information that a solution was found in one of the deeper levels of the recursion tree, and you only get the result for the root.