# The largest binary search subtree of nowcoder

## subject

There is a binary tree in which the values of all nodes are different. Find the search binary tree with the most nodes, and return the head node of this subtree
Given the head node root of a binary tree, please return the head node. If there is a subtree with the most nodes, return the one with the largest weight of the head node.

## thinking

Recursion. Find the head node of the search binary tree of a node's left subtree and right subtree respectively.

## Code

```# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class MaxSubtree:
def getNode(self, root):
if root.left:
lnode, lcount, lMaxNum, lMinNum = self.getNode(root.left)
else:
lnode, lcount, lMaxNum, lMinNum = None, 0, 0, 0
if root.right:
rnode, rcount, rMaxNum, rMinNum = self.getNode(root.right)
else:
rnode, rcount, rMaxNum, rMinNum = None, 0, 0, 0
if lMaxNum < root.val and root.val < rMinNum and lnode == root.left and rnode == root.right:
return root, lcount + rcount + 1, rMaxNum, lMinNum
else:
if lcount == 0 and rcount == 0:
return root, 1, root.val, root.val
if lcount > rcount:
if lMaxNum < root.val and lnode == root.left and rcount == 0:
return root, lcount + 1, root.val, lMinNum
else:
return lnode, lcount, lMaxNum, lMinNum
else:
if root.val < rMinNum and rnode == root.right and lcount == 0:
return root, rcount + 1, rMaxNum, root.val
else:
return rnode, rcount, rMaxNum, rMinNum
def getMax(self, root):
# write code here
node, count, maxNum, minNum = self.getNode(root)
return node```

Posted on Sat, 02 May 2020 04:52:11 -0700 by bills50000